Start by modeling bombs as nodes in a graph where edges exist if one bomb's range covers another. Use depth-first search from each node to simulate detonation chains. The largest chain found across all starting bombs gives the maximum number of bombs that can be detonated.
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.
How GhostInterview Helps
- GhostInterview provides precise DFS-based solutions for chain reactions, preventing missed edge cases.
- It highlights graph construction patterns specific to bomb range interactions.
- Offers visualizable simulation of detonation sequences to verify correctness quickly.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Detonate the Maximum Bombs instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Detonate the Maximum Bombs from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Number of Increasing Paths in a Grid by turning cell comparisons into a DAG and counting paths with topological DP.
Open problem page#2368 Reachable Nodes With RestrictionsIn the 'Reachable Nodes With Restrictions' problem, find the maximum reachable nodes from node 0 in a tree while avoiding restricted nodes.
Open problem page#2467 Most Profitable Path in a TreeSolve the 'Most Profitable Path in a Tree' problem using graph traversal and depth-first search techniques to maximize Alice's net income.
Open problem page