Detect Overlapping VPC CIDR Blocks

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.