Detonate the Maximum Bombs
Medium · Graphs · Explanation and code example
Iterative DFS
How it works
This is the same approach as recursive DFS but uses an explicit stack instead of the call stack. This avoids potential stack overflow issues for very large inputs and can be more efficient in some languages due to reduced function call overhead.
Steps
- Build the adjacency list the same way as before.
- For each bomb as a starting point, initialize a stack with that bomb and a
visitarray. - Pop bombs from the stack: for each bomb, push all unvisited neighbors onto the stack and mark them visited.
- Count all visited bombs and track the maximum across all starting points.
Complexity
- Time complexity:
O(n ^ 3) - Space complexity:
O(n ^ 2)
Things to watch for
Treating the Graph as Undirected
A common mistake is assuming that if bomb A can trigger bomb B, then B can also trigger A. This is incorrect because bombs have different radii. The graph is directed: an edge from A to B exists only if B is within A's blast radius.
Integer Overflow When Computing Distance
When calculating the squared distance between bombs, the intermediate values can overflow 32-bit integers. Coordinates can be up to 10^5 and squaring the difference can exceed INT_MAX. Always use 64-bit integers for distance calculations.
Using Square Root for Distance Comparison
Computing the actual Euclidean distance using sqrt() introduces floating-point precision errors. Instead, compare squared distances directly to avoid precision issues.
Python code example
class Solution:
def maximumDetonation(self, bombs: list[list[int]]) -> int:
n = len(bombs)
adj = [[] for _ in range(n)]
for i in range(n):
x1, y1, r1 = bombs[i]
for j in range(i + 1, n):
x2, y2, r2 = bombs[j]
d = (x1 - x2) ** 2 + (y1 - y2) ** 2
if d <= r1 ** 2:
adj[i].append(j)
if d <= r2 ** 2:
adj[j].append(i)
res = 0
for i in range(n):
stack = [i]
visit = [False] * n
visit[i] = True
count = 1
while stack:
node = stack.pop()
for nei in adj[node]:
if not visit[nei]:
visit[nei] = True
count += 1
stack.append(nei)
res = max(res, count)
return res
C++ code example
class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
vector<vector<int>> adj(n);
for (int i = 0; i < n; i++) {
int x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
for (int j = i + 1; j < n; j++) {
int x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2];
long long d = (long long)(x1 - x2) * (x1 - x2) + (long long)(y1 - y2) * (y1 - y2);
if (d <= (long long) r1 * r1) adj[i].push_back(j);
if (d <= (long long) r2 * r2) adj[j].push_back(i);
}
}
int res = 0;
for (int i = 0; i < n; i++) {
stack<int> stk;
vector<bool> visit(n, false);
stk.push(i);
visit[i] = true;
int count = 1;
while (!stk.empty()) {
int node = stk.top();stk.pop();
for (int& nei : adj[node]) {
if (!visit[nei]) {
visit[nei] = true;
count++;
stk.push(nei);
}
}
}
res = max(res, count);
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.