Detonate the Maximum Bombs

medium graph dfs bfs geometry

Problem

You are given a list of bombs, where each bomb is described as [x, y, r]: it sits at point (x, y) and, when triggered, detonates every bomb whose center lies within its blast radius r. A detonation chains: any bomb caught in a blast then sets off the bombs in its own range, and so on. Pick one bomb to detonate manually and return the maximum number of bombs that can explode.

Note the relationship is directed: bomb A reaching bomb B does not mean B can reach A, because the radii can differ.

Inputbombs = [[2,1,3],[6,1,4]]

Output2

The two centers are 4 apart. Bomb 0 has radius 3, so it cannot reach bomb 1. Bomb 1 has radius 4, so detonating it reaches bomb 0 as well — 2 bombs total.

bombs (x,y,r; ...)

def maximum_detonation(bombs):
    n = len(bombs)
    adj = [[] for _ in range(n)]
    for i in range(n):
        xi, yi, ri = bombs[i]
        for j in range(n):
            if i == j:
                continue
            xj, yj, _ = bombs[j]
            dx, dy = xi - xj, yi - yj
            if dx * dx + dy * dy <= ri * ri:
                adj[i].append(j)
    best = 0
    for start in range(n):
        seen = set([start])
        stack = [start]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
        best = max(best, len(seen))
    return best

function maximumDetonation(bombs) {
  const n = bombs.length;
  const adj = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) {
    const [xi, yi, ri] = bombs[i];
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const dx = xi - bombs[j][0], dy = yi - bombs[j][1];
      if (dx * dx + dy * dy <= ri * ri) adj[i].push(j);
    }
  }
  let best = 0;
  for (let start = 0; start < n; start++) {
    const seen = new Set([start]);
    const stack = [start];
    while (stack.length) {
      const u = stack.pop();
      for (const v of adj[u]) {
        if (!seen.has(v)) { seen.add(v); stack.push(v); }
      }
    }
    best = Math.max(best, seen.size);
  }
  return best;
}

class Solution {
    public int maximumDetonation(int[][] bombs) {
        int n = bombs.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                long dx = xi - bombs[j][0], dy = yi - bombs[j][1];
                if (dx * dx + dy * dy <= ri * ri) adj.get(i).add(j);
            }
        }
        int best = 0;
        for (int start = 0; start < n; start++) {
            boolean[] seen = new boolean[n];
            Deque<Integer> stack = new ArrayDeque<>();
            seen[start] = true; stack.push(start);
            int count = 1;
            while (!stack.isEmpty()) {
                int u = stack.pop();
                for (int v : adj.get(u)) {
                    if (!seen[v]) { seen[v] = true; count++; stack.push(v); }
                }
            }
            best = Math.max(best, count);
        }
        return best;
    }
}

int maximumDetonation(vector<vector<int>>& bombs) {
    int n = bombs.size();
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        long long xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            long long dx = xi - bombs[j][0], dy = yi - bombs[j][1];
            if (dx * dx + dy * dy <= ri * ri) adj[i].push_back(j);
        }
    }
    int best = 0;
    for (int start = 0; start < n; start++) {
        vector<bool> seen(n, false);
        vector<int> stack{ start };
        seen[start] = true;
        int count = 1;
        while (!stack.empty()) {
            int u = stack.back(); stack.pop_back();
            for (int v : adj[u]) {
                if (!seen[v]) { seen[v] = true; count++; stack.push_back(v); }
            }
        }
        best = max(best, count);
    }
    return best;
}

Explanation

Each bomb can trigger another bomb only if the other bomb's center sits inside its blast circle. That gives us a clean way to think about the problem as a graph: put a directed edge from bomb i to bomb j whenever j is within i's radius.

The key subtlety is that these edges are one-directional. If bomb i has a big radius and bomb j a tiny one, i may reach j while j cannot reach i. So we build a directed graph, not an undirected one.

To decide whether i reaches j we compare the distance between centers to the radius. To avoid floating-point square roots we compare the squared distance to the squared radius: (xi − xj)² + (yi − yj)² ≤ ri². That keeps the math in exact integers.

Once the graph is built, the question "how many bombs explode if I trigger bomb s?" is simply "how many nodes are reachable from s?". A depth-first (or breadth-first) traversal from s counts exactly those nodes. We run that traversal from every starting bomb and keep the largest reachable count.

Example: bombs = [[2,1,3],[6,1,4]]. The squared distance between the two centers is (2−6)² + (1−1)² = 16. Bomb 0 has r² = 9 < 16, so no edge 0→1. Bomb 1 has r² = 16 ≤ 16, so edge 1→0 exists. Starting from bomb 0 reaches only itself (1 bomb); starting from bomb 1 reaches bomb 0 too (2 bombs). The answer is 2.

Time: O(n³) Space: O(n²)