Detonate the Maximum Bombs

Medium
943.

Detonate the Maximum Bombs

Detonate the Maximum Bombs is a medium coding problem on arrays, math and depth-first search, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} bombs
 * @return {number}
 */
var maximumDetonation = function(bombs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Detonate the Maximum Bombs — Solution in Python, Java & C++

Detonate the Maximum Bombs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Detonate the Maximum Bombs is a medium coding problem on arrays, math and depth-first search, asked in Amazon, Google and Flipkart interviews.

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

Hints for Detonate the Maximum Bombs

  1. Hint 1

    "Bomb i sets off bomb j" is a directed relation — reach is not symmetric when the radii differ.

  2. Hint 2

    Build that directed graph, then the answer is the largest set reachable from a single node.

  3. Hint 3

    Compare squared distances so no square root is needed.

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

Java

public static 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++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            long dx = bombs[i][0] - bombs[j][0];
            long dy = bombs[i][1] - bombs[j][1];
            long r = bombs[i][2];
            if (dx * dx + dy * dy <= r * r) adj.get(i).add(j);
        }
    }
    int best = 0;
    int[] stack = new int[n];
    for (int s = 0; s < n; s++) {
        boolean[] seen = new boolean[n];
        seen[s] = true;
        int top = 0, count = 0;
        stack[top++] = s;
        while (top > 0) {
            int u = stack[--top];
            count++;
            for (int v : adj.get(u)) {
                if (seen[v]) continue;
                seen[v] = true;
                stack[top++] = v;
            }
        }
        best = Math.max(best, count);
    }
    return best;
}

C++

int maximumDetonation(vector<vector<int>>& bombs) {
    int n = (int) bombs.size();
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            long long dx = bombs[i][0] - bombs[j][0];
            long long dy = bombs[i][1] - bombs[j][1];
            long long r = bombs[i][2];
            if (dx * dx + dy * dy <= r * r) adj[i].push_back(j);
        }
    }
    int best = 0;
    for (int s = 0; s < n; s++) {
        vector<char> seen(n, 0);
        seen[s] = 1;
        vector<int> stack = { s };
        int count = 0;
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            count++;
            for (int v : adj[u]) {
                if (seen[v]) continue;
                seen[v] = 1;
                stack.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)