Detonate the Maximum Bombs

Detonate the Maximum Bombs

What is this problem about?

The Detonate the Maximum Bombs coding problem gives you a list of bombs on a 2D plane. Each bomb is represented as $(x, y, r)$, where $r$ is its blast radius. If one bomb detonates and another bomb is within its radius, the second bomb also detonates. You want to find the maximum number of bombs that can be detonated if you start by triggering exactly one bomb.

Why is this asked in interviews?

Uber and Microsoft ask this to test your ability to model a geometric problem as a graph. It’s a "Connectivity" problem. Even though it involves distances, the relationship between bombs is directed (Bomb A can reach B, but B might not reach A). It evaluations your proficiency with BFS or DFS and your understanding of the distance formula.

Algorithmic pattern used

This problem uses Graph Construction and Graph Traversal (DFS/BFS).

1. Build Graph: Treat each bomb as a node. Add a directed edge from Bomb $i$ to Bomb $j$ if the distance between them is $\le$ radius of $i$. Distance formula: $\sqrt{(x1-x2)^2 + (y1-y2)^2} \le r$.
2. Traverse: For every single bomb, start a DFS/BFS to see how many nodes are reachable.
3. Result: The answer is the maximum reachability found across all nodes.

Example explanation

Bomb 1: (0,0,5), Bomb 2: (3,0,1).

1. Dist(1,2) = 3. $3 \le 5 \implies$ Bomb 1 can trigger 2.
2. Dist(2,1) = 3. $3 > 1 \implies$ Bomb 2 cannot trigger 1.
3. Trigger 1: Detonates {1, 2}. Count = 2.
4. Trigger 2: Detonates {2}. Count = 1. Max = 2.

Common mistakes candidates make

• Using Square Root: To avoid precision issues, use $dx^2 + dy^2 \le r^2$.
• Undirected Graph: Assuming that if A triggers B, then B must trigger A. This is incorrect because their radii might be different.
• Inefficient Search: Trying to use Union Find. Union Find only works for undirected graphs (symmetric relationships). Since this graph is directed, you must use DFS or BFS.

Interview preparation tip

When building graphs from coordinates, always consider the density. Since $N$ is usually small ($< 1000$) in this problem, an $O(N^2)$ graph construction is perfectly fine.