MediumArrayMathDepth-First SearchBreadth-First SearchGraphGeometryUpdated Sep 2026

2101. Detonate the Maximum Bombs

Asked at Airbnb

Difficulty

Medium

Time

O(n^3)

Space

O(n^2)

Pattern

Array

Companies

1

Problem

You are given a list of bombs. Each bomb i is described by bombs[i] = [xi, yi, ri]: it sits at point (xi, yi) and its blast covers a circle of radius ri around that point.

You may set off exactly one bomb by hand. When a bomb explodes, it also sets off every bomb whose center lies inside its blast circle. Those bombs explode too, and they can trigger more bombs in turn. This chain reaction keeps going until no new bomb is reached.

Return the largest number of bombs that can explode if you pick the best single bomb to start with. Note that the relation is one-way: a bomb with a big radius can reach a bomb with a small radius, but not the other way around.

One bomb starts a chain reaction

bombs[2,1,3][6,1,4]01bombs[1] = [6,1,4] is the good starting pointstart bomb 1 at (6,1), r=4distance to bomb 0 = 4 <= 4bomb 0 explodes toototal = 2Detonating bomb 1 pulls bomb 0 into the blast, so 2bombs explode.
Bomb 1 has a wide radius that covers bomb 0, but bomb 0's smaller radius cannot reach back.

Constraints

  • ●1 <= bombs.length <= 100
  • ●bombs[i].length == 3
  • ●1 <= xi, yi, ri <= 10^5

Examples

Example 1
Inputbombs = [[2,1,3],[6,1,4]]
Output2
WhyBomb 0 sits at (2,1) with radius 3, so it reaches x = 5 at most and cannot touch bomb 1 at (6,1). Bomb 1 has radius 4 and reaches down to x = 2, so it covers bomb 0. Starting with bomb 1 explodes both bombs, which beats starting with bomb 0 (only 1 bomb).
Example 2
Inputbombs = [[1,1,5],[10,10,5]]
Output1
WhyThe two centers are far apart (about 12.7 units) and each radius is only 5, so neither bomb reaches the other. Whichever bomb you pick, only that one explodes.
Example 3
Inputbombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output5
WhyStart with bomb 0: it reaches bombs 1 and 2. Bomb 2 then reaches bomb 3, and bomb 3 reaches bomb 4. The chain covers all 5 bombs, so the answer is 5.

Asked At

1 companies
CompanyDifficulty
AirbnbMediumView all Airbnb questions →

How to Think About It

1

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.

2

Once the graph is built, detonating bomb s explodes exactly the set of bombs reachable from s.

3

Key insight: with n <= 100, simply run BFS/DFS from every bomb and take the largest reachable set: O(n³) in the worst case.

4

Use 64-bit arithmetic for squared distances: coordinates and radii up to 10^5 give values up to 10^10.

5

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

Build a directed graph, then BFS from every bomb

check dist^2(i,j) <= ri^2add edge i -> jBFS from each start skeep the largest countCompare squared distances to avoid square roots, thenBFS from each bomb and take the best count.(xi-xj)^2 + (yi-yj)^2 <= ri^2answer = max over s of BFS(s)
An edge i -> j exists when bomb j's center is inside bomb i's circle; the answer is the biggest reachable set.
ComplexityTime O(n^3)Space O(n^2)Building the graph checks all n^2 pairs, and running a BFS from each of the n bombs walks up to n^2 edges; the adjacency lists store up to n^2 edges.

What Trips People Up in Real Interviews

1

Building an undirected graph or using union-find. Reachability depends on the source bomb's radius only.

2

32-bit overflow when squaring coordinates in C++/Java.

3

Using floating-point sqrt for the distance check instead of comparing squares.

4

Reusing the visited array across different starting bombs.

Solution Code

O(n^3) time
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 best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n^3) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.