Get started

Detonate the Maximum Bombs — Medium Problem & Solution

bombs[i] = [x, y, r] places a bomb at (x, y) whose blast is a circle of radius r.

Problem statement

bombs[i] = [x, y, r] places a bomb at (x, y) whose blast is a circle of radius r. Detonating a bomb sets off every bomb whose centre lies inside or on its blast circle, and those set off more in turn.

You may detonate exactly one bomb by hand. Return the maximum number of bombs that can go off.

Example 1

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation: Bomb 1's range reaches bomb 0, but not the other way round.

Example 2

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation: Neither reaches the other.

Example 3

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5

Constraints

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • 1 <= x, y, r <= 10^4

How to solve Detonate the Maximum Bombs

Draw a directed edge i → j when j's centre is within i's radius. The answer is the size of the largest reachable set from any single starting node, found by running a traversal from each bomb.

Approach

  1. For each ordered pair, add the edge when dx² + dy² <= r_i².
  2. From each bomb, run a depth-first or breadth-first search and count what it reaches.
  3. Return the largest count.

Why it works

The relation is directed, which is the whole trap: a big bomb can trigger a small one without the reverse being true, so connected components are the wrong tool and each start must be explored separately. Squaring both sides keeps the comparison in exact integers — with x, y, r <= 10^4 the largest value is 2 · (10^4)², comfortably inside a 32-bit int.

Complexity

  • Time — O(n³) in the worst case — n traversals over n² edges
  • Space — O(n²)

Pitfalls

  • Treating the reach as symmetric collapses the graph and over-counts.
  • Using sqrt invites floating-point error at the boundary; compare squares.
  • A bomb inside its own radius is not an extra bomb; skip i == j.

Reference solution

Python

from typing import List

def maximumDetonation(bombs: List[List[int]]) -> int:
    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
            dx = xi - bombs[j][0]
            dy = yi - bombs[j][1]
            if dx * dx + dy * dy <= ri * ri:
                adj[i].append(j)
    best = 0
    for s in range(n):
        seen = [False] * n
        seen[s] = True
        stack = [s]
        count = 0
        while stack:
            u = stack.pop()
            count += 1
            for v in adj[u]:
                if seen[v]:
                    continue
                seen[v] = True
                stack.append(v)
        best = max(best, count)
    return best

JavaScript

var maximumDetonation = function(bombs) {
    var n = bombs.length, i, j;
    var adj = [];
    for (i = 0; i < n; i++) adj.push([]);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i === j) continue;
            var dx = bombs[i][0] - bombs[j][0];
            var dy = bombs[i][1] - bombs[j][1];
            var r = bombs[i][2];
            if (dx * dx + dy * dy <= r * r) adj[i].push(j);
        }
    }
    var best = 0;
    for (var s = 0; s < n; s++) {
        var seen = [];
        for (i = 0; i < n; i++) seen.push(false);
        seen[s] = true;
        var stack = [s];
        var count = 0;
        while (stack.length > 0) {
            var u = stack.pop();
            count++;
            for (i = 0; i < adj[u].length; i++) {
                var v = adj[u][i];
                if (seen[v]) continue;
                seen[v] = true;
                stack.push(v);
            }
        }
        if (count > best) best = count;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue