# Detonate the Maximum Bombs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/detonate-the-maximum-bombs)
Canonical: https://scaleengineer.com/dsa/problems/detonate-the-maximum-bombs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Graph
**Companies:** [Chime](https://scaleengineer.com/companies/chime)
---
## Problem
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:**

![](https://assets.glich.co/dsa/detonate-the-maximum-bombs/image0.png) 

**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:**

![](https://assets.glich.co/dsa/detonate-the-maximum-bombs/image1.png) 

**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:**

![](https://assets.glich.co/dsa/detonate-the-maximum-bombs/image2.png) 

**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 <= 100`
* `bombs[i].length == 3`
* `1 <= xi, yi, ri <= 105`

# Approaches
## Naive Recursive Simulation
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.
**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.
**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.
### Explanation
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.

```java
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);
                }
            }
        }
    }
}
```
### Algorithm
- Initialize a variable `maxBombs` to 0.
- Iterate through each bomb `i` from `0` to `n-1`, considering it as the starting point for a chain reaction.
- For each starting bomb `i`:
  - Create a `visited` set to keep track of bombs detonated in the current chain.
  - Call a recursive DFS-like helper function, `detonate(i, visited, bombs)`.
- The `detonate(u, visited, bombs)` function:
  - Adds the current bomb `u` to the `visited` set.
  - Iterates through all other bombs `v` in the input array.
  - For each `v`, if it hasn't been visited, it calculates the distance between `u` and `v`.
  - If `v` is within `u`'s range, it makes a recursive call: `detonate(v, visited, bombs)`.
- After the initial `detonate` call for starting bomb `i` completes, the size of the `visited` set represents the total number of bombs detonated.
- Update `maxBombs = max(maxBombs, visited.size())`.
- After checking all bombs as starting points, return `maxBombs`.

## Graph Pre-computation and Traversal
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.
**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)`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- **Graph Construction**:
  - Create an adjacency list, `adj`, to represent the graph, where `adj[i]` will store a list of bombs detonated by bomb `i`.
  - 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 from `i` to `j` in the adjacency list.
- **Traversal**:
  - Initialize `maxBombs = 0`.
  - Iterate through each bomb `i` from `0` to `n-1`, treating it as the starting node.
  - For each `i`, perform a graph traversal (BFS or DFS) starting from `i` to find all reachable nodes.
  - Use a `visited` set for each traversal to count unique bombs in the current chain reaction.
  - For BFS: Use a queue. Add `i` to the queue and `visited` set. 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 the `visited` set.
- **Result**:
  - After each traversal, the size of the `visited` set is the number of bombs detonated. Update `maxBombs` with the maximum size found.
  - Return `maxBombs`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```