Watch 10 video solutions for Detonate the Maximum Bombs, a medium level problem involving Array, Math, Depth-First Search. This walkthrough by NeetCodeIO has 18,015 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.
The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.
You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.
Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.
Example 1:
Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So the maximum bombs that can be detonated is max(1, 2) = 2.
Example 2:
Input: bombs = [[1,1,5],[10,10,5]] Output: 1 Explanation: Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.
Example 3:
Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]] Output: 5 Explanation: The best bomb to detonate is bomb 0 because: - Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0. - Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2. - Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3. Thus all 5 bombs are detonated.
Constraints:
1 <= bombs.length <= 100bombs[i].length == 31 <= xi, yi, ri <= 105Problem Overview: You are given a list of bombs where each bomb has an (x, y) coordinate and a blast radius. If one bomb explodes, it detonates any other bomb inside its radius, potentially causing a chain reaction. The goal is to determine the maximum number of bombs that can explode if you choose the best bomb to detonate first.
Approach 1: Graph Representation with BFS (O(n²) time, O(n²) space)
Model the bombs as a directed graph. Each bomb is a node, and you add a directed edge from bomb i to bomb j if the distance between them is within the blast radius of i. The distance check uses geometry: (x1-x2)^2 + (y1-y2)^2 <= r^2. Building this adjacency list requires checking every pair of bombs, which costs O(n²). After constructing the graph, run a Breadth-First Search from every bomb to simulate the chain reaction and count how many nodes are reachable. Track the maximum visited count across all starting nodes.
BFS works well because the explosion spreads level by level across reachable bombs. A queue stores bombs that get triggered next, and a visited set prevents re-processing the same bomb. Each BFS traversal visits at most n nodes and edges, keeping the total runtime bounded by O(n²).
Approach 2: Graph Representation with DFS (O(n²) time, O(n²) space)
The same graph model can be explored using Depth-First Search. After constructing the adjacency list, start a DFS from each bomb and recursively trigger all bombs reachable through outgoing edges. Maintain a visited set during each traversal to avoid infinite loops and duplicate counts.
DFS explores the entire detonation chain by going as deep as possible before backtracking. Each traversal effectively simulates a full cascade starting from a single bomb. Because the graph contains at most n² edges from pairwise distance checks, the overall complexity remains O(n²) time and O(n²) space for the adjacency list.
The key insight is converting the geometric reachability condition into a directed graph problem. Once the connections are built, the problem reduces to counting reachable nodes using standard graph traversal. Problems combining arrays, geometry distance checks, and graph traversal frequently follow this pattern.
Recommended for interviews: Build the adjacency list and run BFS or DFS from every bomb. Interviewers expect you to recognize the graph structure and use traversal to simulate the chain reaction. Explaining the pairwise distance check shows understanding of the geometry constraint, while implementing BFS or DFS demonstrates strong graph fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph + BFS Traversal | O(n²) | O(n²) | General solution. Easy to visualize chain reactions level by level. |
| Graph + DFS Traversal | O(n²) | O(n²) | Useful when recursion is preferred for exploring full detonation paths. |