Detonate Maximum Bombs ā
Problem Statement ā
You are given a list of bombs on a 2D plane. Each bomb is defined as [x, y, r] where (x, y) is the position and r is the blast radius. When a bomb detonates, it triggers all other bombs within its blast radius (Euclidean distance <= r). Those bombs then detonate and may trigger further bombs in a chain reaction.
Return the maximum number of bombs that can be detonated if you choose to detonate one bomb optimally.
Example 1:
Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation: Detonating bomb 0 ā distance to bomb 1 is 4, radius of bomb 0 is 3.
4 > 3, so bomb 1 is NOT triggered. Detonating bomb 1 ā distance to bomb 0 is 4,
radius of bomb 1 is 4. 4 <= 4, so bomb 0 IS triggered. Total: 2.Example 2:
Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation: No bomb can reach the other.Constraints:
1 <= bombs.length <= 100bombs[i].length == 31 <= x, y, r <= 10^5
Difficulty: Medium (LC 2101)
Pattern Recognition ā
- What is the input structure? A list of points with radii ā geometrical objects with a "reachability" relation.
- What are we optimizing? The maximum number of nodes reachable from a single starting node in a chain.
- What pattern does this fit? Graph construction + BFS/DFS. Build a directed graph where an edge from bomb A to bomb B exists if A's blast radius reaches B. Then find the start node with the maximum reachable set.
- Why does this pattern fit? The "can trigger" relationship is directional (A can reach B does not mean B can reach A ā different radii). This is a directed graph reachability problem.
Approach ā
Brute Force ā Try All Pairs with Simulation ā
For each bomb, simulate the chain reaction using repeated scans until no new bombs are detonated.
Time: O(n^3) ā for each starting bomb, each round scans all n bombs, up to n rounds. Space: O(n). Why insufficient: Although n <= 100 makes this feasible, it is inelegant and harder to reason about correctness.
Optimal ā Directed Graph + BFS/DFS ā
Key Insight: Build the adjacency list once. Bomb A has an edge to bomb B if
(xA - xB)^2 + (yA - yB)^2 <= rA^2. Then the problem reduces to: find the node from which BFS/DFS reaches the most nodes.
Step-by-step:
- Build a directed graph: for each pair (i, j), add edge i ā j if bomb i's radius reaches bomb j.
- For each bomb, run BFS/DFS to count how many bombs are reachable.
- Return the maximum count.
function maxDetonation(bombs):
n = len(bombs)
graph = adjacency list
for i in 0..n-1:
for j in 0..n-1:
if i != j and dist(i, j) <= bombs[i].r:
graph[i].add(j)
best = 0
for i in 0..n-1:
count = bfs(graph, i)
best = max(best, count)
return bestTime: O(n^2) for graph construction + O(n * (n + n^2)) = O(n^3) for n BFS traversals. Since n <= 100, this is ~10^6 operations ā very fast. Space: O(n^2) for the adjacency list.
Walkthrough ā
bombs = [[1,1,3], [5,1,2], [5,5,1], [8,1,4]]Step 1 ā Build graph (check all pairs):
| Pair | Distance | Radius of source | Edge? |
|---|---|---|---|
| 0ā1 | sqrt((5-1)^2 + 0^2) = 4 | r0 = 3 | 4 > 3 ā No |
| 0ā2 | sqrt(16+16) = 5.66 | r0 = 3 | No |
| 0ā3 | sqrt(49+0) = 7 | r0 = 3 | No |
| 1ā0 | 4 | r1 = 2 | 4 > 2 ā No |
| 1ā2 | sqrt(0+16) = 4 | r1 = 2 | No |
| 1ā3 | sqrt(9+0) = 3 | r1 = 2 | No |
| 2ā1 | 4 | r2 = 1 | No |
| 2ā3 | sqrt(9+16) = 5 | r2 = 1 | No |
| 3ā0 | 7 | r3 = 4 | No |
| 3ā1 | 3 | r3 = 4 | 3 <= 4 ā Yes |
| 3ā2 | 5 | r3 = 4 | No |
Graph: {3: [1]} ā only edge is 3 ā 1.
Step 2 ā BFS from each bomb:
| Start | BFS Visited | Count |
|---|---|---|
| 0 | 1 | |
| 1 | 1 | |
| 2 | 1 | |
| 3 | 2 |
Answer: 2 ā start at bomb 3, which triggers bomb 1.
Implementation ā
function maximumDetonation(bombs: number[][]): number {
const n = bombs.length;
const graph: number[][] = Array.from({ length: n }, () => []);
// Build directed graph ā edge iāj if bomb i can reach bomb j
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j) continue;
const dx = bombs[i][0] - bombs[j][0];
const dy = bombs[i][1] - bombs[j][1];
// Compare squared distance to avoid floating point
if (dx * dx + dy * dy <= bombs[i][2] * bombs[i][2]) {
graph[i].push(j);
}
}
}
function bfs(start: number): number {
const visited = new Set<number>([start]);
const queue: number[] = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head++];
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return visited.size;
}
let best = 0;
for (let i = 0; i < n; i++) {
best = Math.max(best, bfs(i));
}
return best;
}int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
vector<vector<int>> graph(n);
// Build directed graph ā edge iāj if bomb i can reach bomb j
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
long long dx = bombs[i][0] - bombs[j][0];
long long dy = bombs[i][1] - bombs[j][1];
long long r = bombs[i][2];
// Compare squared distance to avoid floating point
if (dx * dx + dy * dy <= r * r) {
graph[i].push_back(j);
}
}
}
auto bfs = [&](int start) -> int {
vector<bool> visited(n, false);
visited[start] = true;
queue<int> q;
q.push(start);
int count = 1;
while (!q.empty()) {
int node = q.front(); q.pop();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
count++;
}
}
}
return count;
};
int best = 0;
for (int i = 0; i < n; i++) {
best = max(best, bfs(i));
}
return best;
}Watch out:
- Using Euclidean distance with
sqrtintroduces floating-point error. Comparedx^2 + dy^2 <= r^2instead. This is exact for integers. - Making the graph undirected. Bomb A reaching B does not mean B reaches A ā their radii differ. The graph must be directed.
- Integer overflow when squaring coordinates. With
x, y, rup to 10^5, the squared values reach 10^10. In Python this is fine (arbitrary precision), but in languages like Java/C++ uselong.
Follow-up: Directed Graph Variation ā
A common follow-up asks: What if detonated bombs strengthen nearby bombs? For example, when bomb A detonates bomb B, bomb B's effective radius increases by some factor. This changes the graph dynamically.
Approach: You can no longer precompute the graph. Instead, during BFS/DFS, when you "detonate" a bomb, recompute which additional bombs it can now reach with its enhanced radius. This turns the problem into a modified BFS where the graph is constructed on the fly.
function maximumDetonationEnhanced(bombs: number[][]): number {
const n = bombs.length;
function bfsDynamic(start: number): number {
const visited = new Set<number>([start]);
const queue: number[] = [start];
let head = 0;
while (head < queue.length) {
const node = queue[head++];
const [x1, y1, r1] = bombs[node];
for (let j = 0; j < n; j++) {
if (visited.has(j)) continue;
const dx = x1 - bombs[j][0];
const dy = y1 - bombs[j][1];
if (dx * dx + dy * dy <= r1 * r1) {
visited.add(j);
queue.push(j);
}
}
}
return visited.size;
}
let best = 0;
for (let i = 0; i < n; i++) {
best = Math.max(best, bfsDynamic(i));
}
return best;
}int maximumDetonationEnhanced(vector<vector<int>>& bombs) {
int n = bombs.size();
auto bfsDynamic = [&](int start) -> int {
vector<bool> visited(n, false);
visited[start] = true;
queue<int> q;
q.push(start);
int count = 1;
while (!q.empty()) {
int node = q.front(); q.pop();
long long x1 = bombs[node][0], y1 = bombs[node][1], r1 = bombs[node][2];
for (int j = 0; j < n; j++) {
if (visited[j]) continue;
long long dx = x1 - bombs[j][0];
long long dy = y1 - bombs[j][1];
if (dx * dx + dy * dy <= r1 * r1) {
visited[j] = true;
q.push(j);
count++;
}
}
}
return count;
};
int best = 0;
for (int i = 0; i < n; i++) {
best = max(best, bfsDynamic(i));
}
return best;
}Complexity Analysis ā
| Time | Space | |
|---|---|---|
| Graph Construction | O(n^2) | O(n^2) |
| BFS from all nodes | O(n * (n + E)) where E <= n^2 | O(n) per BFS |
| Overall | O(n^3) | O(n^2) |
Bottleneck: With n <= 100, O(n^3) is approximately 10^6 ā comfortably fast. The graph construction is O(n^2), and running BFS from each of n nodes costs O(n + E) each. In the worst case E = n^2 (every bomb reaches every other), giving O(n^3) total.
Edge Cases ā
- Single bomb ā Return 1. No edges to process.
- No bomb reaches any other ā Each BFS returns 1. Answer is 1.
- All bombs reach all others ā Fully connected graph. Any start gives n. Answer is n.
- Bombs at the same position ā All bombs with any positive radius reach each other. This forms a clique.
- Chain reaction across the entire array ā A ā B ā C ā ... ā Z. Only starting at A gives the full chain. Tests that BFS correctly follows multi-hop paths.
- Large radii with far-apart bombs ā Tests the squared distance comparison for large values.
Related Problems ā
- LC 547 ā Number of Provinces ā Graph connectivity, but undirected. Similar graph-building from pairwise relations.
- LC 1654 ā Minimum Jumps to Reach Home ā BFS on a graph with specific reachability rules.
- LC 802 ā Find Eventual Safe States ā Directed graph analysis, cycle detection.
- LC 1462 ā Course Schedule IV ā Transitive reachability in a directed graph.
What is Expected at Each Level ā
Junior: Recognize the graph structure. Build the adjacency list correctly. Implement BFS. May forget that the graph is directed.
Mid-level: Immediately model as a directed graph. Use squared distances to avoid floating point. Write clean BFS, analyze complexity, and explain why O(n^3) is acceptable for n <= 100.
Senior: Solve quickly and discuss optimizations for larger n: spatial indexing (k-d trees, grid cells) to reduce edge computation to O(n log n). Discuss the follow-up variation. Mention that if we only need the max reachable count, we could potentially prune BFS early if we have already found a result of n.