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.
Represent each bomb as a node in a graph. An edge exists from bomb i to bomb j if bomb i can detonate bomb j. The goal is to start from each bomb and use BFS to find how many bombs can be detonated. Return the maximum number of detonatable bombs starting from any single bomb.
This code constructs a graph with each bomb as a node and checks if a bomb can detonate another based on their respective ranges. BFS is used from each bomb to determine the total number of bombs that can be detonated, and the maximum among all is returned.
Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs.
Space Complexity: O(n), for storing the adjacency list of the graph and the visited list.
Another approach to solve this problem is by using a DFS traversal instead of BFS. We use a similar graph representation where each bomb is a node and an edge exists if one bomb can detonate another. The maximum number of bombs that can be reached starting from each node (bomb) is determined using DFS.
This C++ implementation uses DFS to explore each detonation starting from every bomb and computes the maximum possible detonations. It uses a recursive function to delve deeper into the graph from each bomb until all reachable bombs are visited starting from a given bomb.
C++
JavaScript
Time Complexity: O(n^2) for constructing the graph and performing DFS traversals.
Space Complexity: O(n) used in the recursion stack and the visited vector.
We define an array g of length n, where g[i] represents the indices of all bombs that can be triggered by bomb i within its explosion range.
Next, we iterate over all bombs. For two bombs (x_1, y_1, r_1) and (x_2, y_2, r_2), we calculate the distance between them dist = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}. If dist leq r_1, then bomb i can trigger bomb j within its explosion range, so we add j to g[i]. If dist leq r_2, then bomb j can trigger bomb i within its explosion range, so we add i to g[j].
Next, we iterate over all bombs. For each bomb k, we use breadth-first search to calculate the indices of all bombs that can be triggered by bomb k within its explosion range and record them. If the number of these bombs equals n, then we can trigger all bombs and directly return n. Otherwise, we record the number of these bombs and return the maximum value.
The time complexity is O(n^3) and the space complexity is O(n^2), where n is the number of bombs.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Graph Representation with BFS | Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs. |
| Graph Representation with DFS | Time Complexity: O(n^2) for constructing the graph and performing DFS traversals. |
| BFS | — |
| 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. |
Detonate the Maximum Bombs - Leetcode 2101 - Python • NeetCodeIO • 18,015 views views
Watch 9 more video solutions →Practice Detonate the Maximum Bombs with our built-in code editor and test cases.
Practice on FleetCode