Detect Overlapping VPC CIDR Blocks

mediumFREENetworking & AddressingSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

Two VPCs whose CIDR ranges overlap cannot be peered, and a subnet that overlaps its own VPC's other subnets will be rejected outright. Given the address plan for a cluster, find every colliding pair before Terraform does.

Background

Every CIDR block is a contiguous, power-of-two-sized range of 32-bit integers. Convert each block to [low, high]:

size    = 2 ** (32 - prefix)
network = ip - (ip % size)        # clear the host bits
low, high = network, network + size - 1

Two ranges overlap when low_i <= high_j and low_j <= high_i. That single test covers all three cases that matter: partial overlap, one block fully containing another (10.0.0.0/16 and 10.0.1.0/24), and two identical blocks.

Comparing the strings, or only comparing prefixes, misses containment — which is the case that actually shows up in a VPC plan.

Note the input may carry host bits (10.0.5.7/24 means the block 10.0.5.0/24), so normalise before comparing.

Your Task

Implement:

def find_overlaps(cidrs):

Return a list of [cidrs[i], cidrs[j]] pairs with i < j, in increasing order of i then j, for every overlapping pair. Return [] when the plan is clean.

Input Format

cidrs: list of CIDR strings.

Output Format

A list of two-element lists of the original CIDR strings.

Sample

print(find_overlaps(["10.0.0.0/16", "10.0.1.0/24", "10.1.0.0/16", "192.168.0.0/16"]))

Output:

[['10.0.0.0/16', '10.0.1.0/24']]

10.0.1.0/24 sits entirely inside 10.0.0.0/16, so the pair collides; the other two blocks are disjoint from everything.

Example

Input

print(find_overlaps(["10.0.0.0/16", "10.0.1.0/24", "10.1.0.0/16", "192.168.0.0/16"]))

Output

[['10.0.0.0/16', '10.0.1.0/24']]

Reasoning

Input: four CIDR strings. Each is a dotted address plus a prefix length $p$ , naming a block of $2^{32-p}$ consecutive 32-bit addresses: $2^{16} = 65536$ for a /16, $2^{8} = 256$ for a /24.
Read as one 32-bit number, 10.0.0.0 is $10 \cdot 2^{24} = 167772160$ , so 10.0.0.0/16 spans $[167772160,\ 167837695]$ . 10.0.1.0/24 starts $256$ addresses later and spans $[167772416,\ 167772671]$ .
Overlap test for this pair: $167772160 \le 167772671$ and $167772416 \le 167837695$ . Both hold, so they collide; the /24 sits wholly inside the /16.
10.1.0.0/16 spans $[167837696,\ 167903231]$ . Its low end is exactly one above the first block's high end $167837695$ , so the two touch but share no address. It also clears the /24, since $167772671 < 167837696$ . 192.168.0.0/16 spans $[3232235520,\ 3232301055]$ , far above everything.
Output: a single pair, earlier entry first: [['10.0.0.0/16', '10.0.1.0/24']]. Notice that adjacent blocks are not an overlap, and the pair holds the original strings, not the normalised ranges.

Constraints

0 <= len(cidrs) <= 200
Each entry is a valid IPv4 CIDR, prefix length 0 to 32
Inputs may have host bits set and must be normalised to the network address first
Containment counts as an overlap, as do two identical blocks
Pairs are returned as [cidrs[i], cidrs[j]] with i < j, ordered by i then j

Learn this in

Cloud & AWS EssentialsSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primer

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:

Normalization: Convert each CIDR string to a canonical integer range $[low, high]$ .
Pairwise Comparison: Iterate through all unique pairs $(i, j)$ where $i < j$ .
Overlap Check: Apply the interval intersection logic.
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

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.

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.
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)).

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.

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)$ .

solution.py

Python 3.13

Test results