Detonate the Maximum Bombs
Asked at Airbnb
Problem
Detonate the Maximum Bombs gives you bombs with positions and blast radii. Detonating one bomb sets off every bomb inside its radius, which chain-react. If you can detonate exactly one bomb by hand, what is the most bombs that can explode? Build a directed graph and run a traversal from every bomb.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Medium | View all Airbnb questions → |
How to Think About It
Bomb i triggers bomb j if j is within i's radius: (xi - xj)² + (yi - yj)² <= ri². This is not symmetric — a big bomb can reach a small one that cannot reach back — so the graph is directed.
Once the graph is built, detonating bomb s explodes exactly the set of bombs reachable from s.
Key insight: with n <= 100, simply run BFS/DFS from every bomb and take the largest reachable set: O(n³) in the worst case.
Use 64-bit arithmetic for squared distances: coordinates and radii up to 10^5 give values up to 10^10.
Union-find does not work here, because reachability is directional.
Optimal Approach
Step 1: For every pair (i, j) with i != j, add edge i -> j if dist²(i, j) <= r_i².
Step 2: For each bomb s, BFS from s and count visited bombs.
Step 3: Return the maximum count.
Time: O(n³) worst case (n BFS runs over up to n² edges). Space: O(n²).
What Trips People Up in Real Interviews
Building an undirected graph or using union-find. Reachability depends on the source bomb's radius only.
32-bit overflow when squaring coordinates in C++/Java.
Using floating-point sqrt for the distance check instead of comparing squares.
Reusing the visited array across different starting bombs.
Solution Code
from collections import deque
def maximumDetonation(bombs):
n = len(bombs)
adj = [[] for _ in range(n)]
for i, (xi, yi, ri) in enumerate(bombs):
for j, (xj, yj, _) in enumerate(bombs):
if i != j and (xi - xj) ** 2 + (yi - yj) ** 2 <= ri * ri:
adj[i].append(j)
best = 0
for s in range(n):
seen = [False] * n
seen[s] = True
q = deque([s])
cnt = 1
while q:
u = q.popleft()
for v in adj[u]:
if not seen[v]:
seen[v] = True
cnt += 1
q.append(v)
best = max(best, cnt)
return bestFrequently Asked Questions
What is the Detonate the Maximum Bombs problem?
Detonate the Maximum Bombs gives you bombs with positions and blast radii. Detonating one bomb sets off every bomb inside its radius, which chain-react. If you can detonate exactly one bomb by hand, what is the most bombs that can explode? Build a directed graph and run a traversal from every bomb.
How do you solve Detonate the Maximum Bombs?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Detonate the Maximum Bombs?
Detonate the Maximum Bombs is asked at Airbnb. It is a medium difficulty problem.
What are common mistakes on Detonate the Maximum Bombs?
- Building an undirected graph or using union-find. Reachability depends on the source bomb's radius only.
- 32-bit overflow when squaring coordinates in C++/Java.
- Using floating-point `sqrt` for the distance check instead of comparing squares.
- Reusing the visited array across different starting bombs.