Circle Group Connectivity

Learning Outcome

Turn the Circle Group Connectivity interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

Given circles, decide whether they belong to one connected group through overlaps/tangencies.

Examples

Brute Force Approach

Run DFS from each circle checking all others repeatedly without compression.

Optimized Approach

Use DSU. Two circles connect if center distance is at most r1+r2 and at least abs(r1-r2) if strict boundary-only grouping is required by the variant.

Exact Pseudocode

for every pair of circles:
  if overlap/touch: union(i,j)
answer = number of DSU roots
  

Reference Code

def circle_groups(circles):
    n = len(circles)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
    for i in range(n):
        x1, y1, r1 = circles[i]
        for j in range(i + 1, n):
            x2, y2, r2 = circles[j]
            d2 = (x1 - x2) ** 2 + (y1 - y2) ** 2
            if d2 <= (r1 + r2) ** 2:
                union(i, j)
    return len({find(i) for i in range(n)})
  

Complexity

Edge Cases

• Nested circles
• Tangency exactly
• Disconnected groups

Follow-ups

• Can a path cross from source to target?
• Block rectangle with circles

Nearest Practice References

• Number of Provinces
• Circle overlap DSU

Common Mistakes

• Copying the nearest LeetCode solution without checking the changed rule.
• Skipping duplicate or boundary cases.
• Not stating the brute force before the optimized approach.