#2101

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Detonate the Maximum Bombs

Determine the maximum number of bombs that can be detonated by leveraging chain reactions using graph traversal and DFS logic efficiently.

array math depth first search breadth first search graph

Problem Statement

You are given a 0-indexed list of bombs, each with a 2D location and a detonation radius. A bomb detonates all bombs whose centers lie within its circular range, potentially triggering further chain detonations.

Each bomb is represented as bombs[i] = [xi, yi, ri], where xi and yi are the coordinates and ri is the radius. Determine the maximum number of bombs that can be detonated starting from a single initial bomb.

Examples

Example 1

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

Output: 2

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

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

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

Solution Approach

Model Bombs as a Directed Graph

Create a graph where each bomb is a node and an edge from bomb A to bomb B exists if B is within A's radius. This allows us to represent potential chain reactions explicitly.

Depth-First Search for Detonation Chains

Perform DFS from each bomb node to simulate all bombs that would detonate as a result. Keep track of visited bombs to avoid cycles and to count the total bombs in the chain.

Compute Maximum Detonations

Iterate through all bombs, running DFS from each, and track the largest chain size. The maximum value across all starting bombs is the solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) for graph construction and O(n*(n+n)) for DFS across n bombs, leading to roughly O(n^2). Space complexity is O(n^2) for the adjacency graph plus O(n) for DFS recursion stack.

What Interviewers Usually Probe

Ask how to represent bomb interactions efficiently as a graph.
Check if the candidate considers chain reactions via depth-first traversal.
Probe for optimizations to reduce unnecessary repeated DFS computations.

Common Pitfalls or Variants

Common pitfalls

Not modeling the problem as a graph and attempting range checks repeatedly.
Ignoring cycles or revisiting bombs in DFS, leading to incorrect counts.
Failing to compute maximum across all starting bombs rather than just one path.

Follow-up variants

Consider limiting detonations to bombs within a certain Manhattan distance instead of Euclidean radius.
Calculate minimum number of initial detonations required to trigger all bombs.
Determine which bombs trigger the same maximum chain and report all starting options.

FAQ

What pattern does 'Detonate the Maximum Bombs' primarily use?

The problem relies on graph traversal with depth-first search to model chain detonations efficiently.

How do I determine if one bomb can detonate another?

Check if the distance between centers is less than or equal to the detonating bomb's radius squared to avoid floating-point errors.

Can BFS be used instead of DFS?

Yes, BFS can simulate detonations level by level, but DFS is typically simpler for maximum chain length calculation.

What is the expected time complexity for up to 100 bombs?

Graph construction is O(n^2) and DFS for each bomb is O(n), so overall roughly O(n^2), which is acceptable for n ≤ 100.

Why must we consider all bombs as starting points?

Because the maximum detonation chain may not start from the first or leftmost bomb; the optimal starting bomb must be evaluated.

terminal

Solution

Solution 1: BFS

We define an array $g$ of length $n$, where $g[i]$ represents the indices of all bombs that can be triggered by bomb $i$ within its explosion range.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        g = [[] for _ in range(n)]
        for i in range(n - 1):
            x1, y1, r1 = bombs[i]
            for j in range(i + 1, n):
                x2, y2, r2 = bombs[j]
                dist = hypot(x1 - x2, y1 - y2)
                if dist <= r1:
                    g[i].append(j)
                if dist <= r2:
                    g[j].append(i)
        ans = 0
        for k in range(n):
            vis = {k}
            q = [k]
            for i in q:
                for j in g[i]:
                    if j not in vis:
                        vis.add(j)
                        q.append(j)
            if len(vis) == n:
                return n
            ans = max(ans, len(vis))
        return ans

Continue Practicing

#2328 number of increasing paths in a grid #2368 reachable nodes with restrictions #2467 most profitable path in a tree