Detonate the Maximum Bombs
MedPrompt
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 <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This is a direct simulation of the chain reaction process. For each bomb, we simulate its detonation and the subsequent chain reaction. We use a recursive function that, given a bomb to detonate, finds all other bombs within its range and recursively calls itself on them. We use a set to keep track of all bombs detonated in a single chain reaction to avoid infinite loops and re-processing. We repeat this for every bomb as the starting point and find the maximum number of bombs detonated.
Algorithm
- Initialize a variable
maxBombsto 0. - Iterate through each bomb
ifrom0ton-1, considering it as the starting point for a chain reaction. - For each starting bomb
i:- Create a
visitedset to keep track of bombs detonated in the current chain. - Call a recursive DFS-like helper function,
detonate(i, visited, bombs).
- Create a
- The
detonate(u, visited, bombs)function:- Adds the current bomb
uto thevisitedset. - Iterates through all other bombs
vin the input array. - For each
v, if it hasn't been visited, it calculates the distance betweenuandv. - If
vis withinu's range, it makes a recursive call:detonate(v, visited, bombs).
- Adds the current bomb
- After the initial
detonatecall for starting bombicompletes, the size of thevisitedset represents the total number of bombs detonated. - Update
maxBombs = max(maxBombs, visited.size()). - After checking all bombs as starting points, return
maxBombs.
Walkthrough
This approach directly translates the problem into a recursive simulation without any pre-computation. We test every bomb as a potential starting point. For each start, we perform a Depth-First Search (DFS) to find all bombs that would be detonated in the chain reaction. The key difference from a more optimized graph traversal is that the "neighbors" (bombs in range) are not pre-calculated. Instead, for every bomb in the current explosion path, we iterate through all other bombs to see which ones it can detonate. This on-the-fly calculation of detonation relationships is done within each recursive call.
import java.util.*; class Solution { public int maximumDetonation(int[][] bombs) { int n = bombs.length; int maxBombs = 0; for (int i = 0; i < n; i++) { Set<Integer> visited = new HashSet<>(); dfs(i, visited, bombs); maxBombs = Math.max(maxBombs, visited.size()); } return maxBombs; } private void dfs(int u, Set<Integer> visited, int[][] bombs) { visited.add(u); int n = bombs.length; long x1 = bombs[u][0], y1 = bombs[u][1], r1 = bombs[u][2]; for (int v = 0; v < n; v++) { if (!visited.contains(v)) { long x2 = bombs[v][0], y2 = bombs[v][1]; long dx = x1 - x2; long dy = y1 - y2; if (dx * dx + dy * dy <= r1 * r1) { dfs(v, visited, bombs); } } } }}Complexity
Time
O(n^3) - We iterate through `n` starting bombs. For each, we perform a DFS. In each step of the DFS, we iterate through all `n` bombs to find neighbors. This leads to `n * O(n^2) = O(n^3)` complexity.
Space
O(n) - The space is dominated by the recursion stack depth and the `visited` set, both of which can be at most `n` in size.
Trade-offs
Pros
Conceptually simple and easy to implement as it directly models the problem statement.
Uses less space (
O(n)) compared to the graph pre-computation approach.
Cons
Highly inefficient due to redundant computations. The check to see if one bomb detonates another is repeated many times for the same pair of bombs across different initial simulations.
The time complexity, while technically the same
O(n^3)as the optimized approach in the worst case, has a much larger constant factor, making it slower in practice.
This approach improves efficiency by pre-calculating all possible detonation relationships and storing them in a graph data structure, typically an adjacency list. By doing this, we avoid re-calculating the distances between bombs repeatedly. Once the graph is built, the problem is transformed into a standard graph problem: for each node, find the size of its reachable component. We iterate through each bomb as a starting point and perform a graph traversal (like BFS or DFS) to count the number of reachable bombs, keeping track of the maximum count.
Algorithm
- Graph Construction:
- Create an adjacency list,
adj, to represent the graph, whereadj[i]will store a list of bombs detonated by bombi. - Iterate through all pairs of bombs
(i, j). For each pair, calculate the squared distance between them. - If the squared distance is less than or equal to the squared radius of bomb
i, add a directed edge fromitojin the adjacency list.
- Create an adjacency list,
- Traversal:
- Initialize
maxBombs = 0. - Iterate through each bomb
ifrom0ton-1, treating it as the starting node. - For each
i, perform a graph traversal (BFS or DFS) starting fromito find all reachable nodes. - Use a
visitedset for each traversal to count unique bombs in the current chain reaction. - For BFS: Use a queue. Add
ito the queue andvisitedset. While the queue is not empty, dequeue a bomb, and for each of its unvisited neighbors in the adjacency list, enqueue it and add it to thevisitedset.
- Initialize
- Result:
- After each traversal, the size of the
visitedset is the number of bombs detonated. UpdatemaxBombswith the maximum size found. - Return
maxBombs.
- After each traversal, the size of the
Walkthrough
The core idea is to model the bombs and their detonation capabilities as a directed graph. Each bomb is a vertex. A directed edge exists from bomb i to bomb j if bomb i's explosion range covers bomb j's location.
First, we build this graph. We iterate through every pair of bombs (i, j) and check if i can detonate j. To avoid floating-point issues, we compare squared distances: (xi - xj)^2 + (yi - yj)^2 <= ri^2. Note that long should be used for these squared values to prevent integer overflow. If the condition holds, we add an edge i -> j.
After the O(n^2) graph construction, we iterate through each bomb i and start a graph traversal (BFS is a good choice) from it. The traversal counts all nodes reachable from i. We keep track of the maximum count found across all starting bombs. This count is our answer.
import java.util.*; class Solution { public int maximumDetonation(int[][] bombs) { int n = bombs.length; Map<Integer, List<Integer>> adj = new HashMap<>(); // Step 1: Build the graph for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2]; long x2 = bombs[j][0], y2 = bombs[j][1]; long dx = x1 - x2; long dy = y1 - y2; if (dx * dx + dy * dy <= r1 * r1) { adj.computeIfAbsent(i, k -> new ArrayList<>()).add(j); } } } int maxBombs = 0; if (n == 0) return 0; // Step 2: Traverse from each node for (int i = 0; i < n; i++) { Set<Integer> visited = new HashSet<>(); Queue<Integer> queue = new LinkedList<>(); queue.offer(i); visited.add(i); while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj.getOrDefault(u, new ArrayList<>())) { if (!visited.contains(v)) { visited.add(v); queue.offer(v); } } } maxBombs = Math.max(maxBombs, visited.size()); } return maxBombs; }}Complexity
Time
O(n^3) - Graph construction takes `O(n^2)`. Then, we loop `n` times. Each time, we perform a BFS. A single BFS takes `O(V + E) = O(n + E)`, where `E` can be up to `O(n^2)`. So, the traversal part is `n * O(n^2) = O(n^3)` in the worst case. The total is `O(n^2 + n^3) = O(n^3)`.
Space
O(n^2) - The adjacency list can store up to `O(n^2)` edges in a dense graph. The space for the traversal (queue and visited set) is `O(n)`.
Trade-offs
Pros
More efficient in practice than the naive simulation because the expensive
O(n^2)work of finding detonation relationships is done only once.Represents a standard and robust pattern for solving connectivity and reachability problems (build graph, then traverse).
Cons
Requires more space (
O(n^2)) to store the adjacency list of the graph.The worst-case time complexity is still
O(n^3), which might not be obvious at first glance.
Solutions
Solution
class Solution {private int[][] bombs;public int maximumDetonation(int[][] bombs) { this.bombs = bombs; int n = bombs.length; boolean[][] g = new boolean[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { g[i][j] = check(i, j); } } int ans = 0; for (int k = 0; k < n; ++k) { Deque<Integer> q = new ArrayDeque<>(); q.offer(k); boolean[] vis = new boolean[n]; vis[k] = true; int cnt = 0; while (!q.isEmpty()) { int i = q.poll(); ++cnt; for (int j = 0; j < n; ++j) { if (g[i][j] && !vis[j]) { vis[j] = true; q.offer(j); } } } ans = Math.max(ans, cnt); } return ans; }private boolean check(int i, int j) { if (i == j) { return false; } long x = bombs[i][0] - bombs[j][0]; long y = bombs[i][1] - bombs[j][1]; long r = bombs[i][2]; return r * r >= x * x + y * y; }}class Solution {public: int maximumDetonation(vector<vector<int>> &bombs) { int n = bombs.size(); vector<vector<bool>> g(n, vector<bool>(n)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) g[i][j] = check(i, j, bombs); int ans = 0; for (int k = 0; k < n; ++k) { queue<int> q{{k}}; vector<bool> vis(n); vis[k] = true; int cnt = 0; while (!q.empty()) { int i = q.front(); q.pop(); ++cnt; for (int j = 0; j < n; ++j) { if (g[i][j] && !vis[j]) { vis[j] = true; q.push(j); } } } ans = max(ans, cnt); } return ans; } bool check(int i, int j, vector<vector<int>> &bombs) { if (i == j) return false; long long x = bombs[i][0] - bombs[j][0]; long long y = bombs[i][1] - bombs[j][1]; long long r = bombs[i][2]; return r * r >= x * x + y * y; }};class Solution: def maximumDetonation(self, bombs: List[List[int]]) -> int: def check(i, j): if i == j: return False x, y = bombs[i][0] - bombs[j][0], bombs[i][1] - bombs[j][1] r = bombs[i][2] return r * r >= x * x + y * y g = defaultdict(list) n = len(bombs) for i in range(n): for j in range(n): if check(i, j): g[i]. append(j) ans = 0 for k in range(n): q = deque([k]) vis = [False] * n vis[k] = True cnt = 0 while q: i = q . popleft() cnt += 1 for j in g[i]: if not vis[j]: vis[j] = True q . append(j) ans = max(ans, cnt) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.