Detect Overlapping VPC CIDR Blocks

1. Background Knowledge

CIDR Notation (Classless Inter-Domain Routing) is the standard method for describing IP address ranges. A CIDR block consists of an IP address and a prefix length (e.g., 192.168.1.0/24). The prefix length indicates how many bits of the 32-bit IPv4 address are fixed for the network portion, while the remaining bits represent the host portion. This structure implies that every CIDR block represents a contiguous range of IP addresses with a size that is always a power of two ($2^{32 - \text{prefix}}$).

To compare CIDR blocks effectively, they must be normalized. Input strings may contain "host bits" (e.g., 10.0.5.7/24), which technically refer to a specific host within the 10.0.5.0/24 network. For overlap detection, we must treat this as the entire network block. This requires converting the IP string into a 32-bit integer, masking out the host bits to find the network address, and then calculating the broadcast address (the last IP in the range).

IP Address Conversion involves translating the dotted-decimal format (e.g., 10.0.0.0) into a single integer. This is done by treating each octet as a byte in a big-endian integer. For example, 10.0.0.0 becomes $10 \times 256^3 + 0 \times 256^2 + 0 \times 256^1 + 0 \times 256^0$. Once converted, arithmetic operations can determine the start (low) and end (high) of the range. The range is defined as $[\text{network}, \text{network} + \text{size} - 1]$.

2. Algorithm Approach

The core problem is Interval Overlap Detection. Once CIDR blocks are converted into integer intervals $[low, high]$, the task reduces to finding all pairs of intervals that intersect. Two intervals $[a, b]$ and $[c, d]$ overlap if and only if $a \le d$ and $c \le b$.

Since the input size for typical infrastructure planning problems is moderate (often $N < 1000$), a brute-force comparison of all pairs is acceptable and often simpler to implement correctly than more complex interval tree or sweep-line algorithms. The approach involves:

1. Normalization: Convert each CIDR string to a canonical integer range $[low, high]$.
2. Pairwise Comparison: Iterate through all unique pairs $(i, j)$ where $i < j$.
3. Overlap Check: Apply the interval intersection logic.
4. Result Construction: If an overlap is found, store the original CIDR strings in the result list, maintaining the required order.

3. Step-by-Step Strategy

1. Helper Function for IP Parsing: Create a function to convert a CIDR string (e.g., "10.0.0.0/16") into a tuple (low, high).

• Split the string by / to get the IP part and the prefix length.
• Convert the IP part to an integer. Split by ., map each octet to an integer, and combine using bitwise shifts or multiplication by powers of 256.
• Calculate the size of the block: $2^{(32 - \text{prefix})}$.
• Calculate the network address (the low bound) by clearing the host bits. This can be done using bitwise AND with a mask: ip & (~((1 << (32 - prefix)) - 1)) or simply ip - (ip % size).
• Calculate the high bound: network + size - 1.

2. Preprocessing: Iterate through the input cidrs list. For each CIDR, compute its (low, high) range. Store these ranges in a list, keeping track of their original indices to ensure correct output ordering.

3. Nested Loop for Comparison: Use two nested loops to compare every pair of ranges.

• Outer loop i from 0 to N-1.
• Inner loop j from i+1 to N-1.
• This ensures $i < j$ and avoids duplicate checks (e.g., checking pair (0,1) and then (1,0)).

4. Overlap Logic: For each pair of ranges (low_i, high_i) and (low_j, high_j), check if they overlap:

if low_i <= high_j and low_j <= high_i:
# Overlap detected

If true, append [cidrs[i], cidrs[j]] to the results list.

5. Return Results: Return the accumulated list of overlapping pairs. The nested loop structure naturally guarantees the output is sorted by index $i$ then $j$.

4. Common Pitfalls

• Ignoring Host Bits: A common error is assuming the IP part of the CIDR is always the network address. 10.0.0.5/24 is valid input but represents the same network as 10.0.0.0/24. Failing to normalize (mask out host bits) will lead to incorrect low values and missed overlaps.
• Off-by-One Errors: When calculating the high bound, remember that the range is inclusive. The last address is network + size - 1. Using network + size will incorrectly extend the range by one IP.
• Integer Overflow: While Python handles large integers automatically, in other languages, 32-bit IP addresses fit in standard integers. Ensure you use unsigned 32-bit arithmetic logic if porting to C++ or Java.
• String Comparison: Never compare CIDR strings lexicographically. "10.0.0.0/16" and "10.0.1.0/24" might look similar, but their numeric ranges determine overlap.
• Ordering: The problem requires pairs with $i < j$. Ensure your loops enforce this strict ordering to avoid duplicates like ['A', 'B'] and ['B', 'A'].

5. Time & Space Complexity

• Time Complexity: $O(N^2 \cdot L)$, where $N$ is the number of CIDR blocks and $L$ is the length of the CIDR string (for parsing). The nested loops compare every pair, resulting in $N(N-1)/2$ comparisons. Parsing each CIDR takes constant time relative to the fixed 32-bit IP structure, but technically depends on string length. For typical infrastructure sizes ($N \le 1000$), this is efficient enough.
• Space Complexity: $O(N)$ to store the precomputed (low, high) ranges for each CIDR block. The output list can also take up to $O(N^2)$ space in the worst case (all blocks overlap), but this is part of the required output, not auxiliary space. Auxiliary space is $O(N)$.