Detonate the Maximum Bombs
01 · Problem
You are given a list of bombs, where bombs[i] = [x, y, r] places a bomb at integer point (x, y) with blast radius r. When a bomb explodes, every bomb whose centre lies within or exactly on the edge of its blast circle (Euclidean distance <= r) also explodes, and those explosions can trigger further bombs in a chain.
Note that reach is not symmetric: bomb A reaching bomb B does not imply B reaches A, because their radii may differ.
You may manually set off exactly one bomb. Return the maximum total number of bombs that can explode, including the one you set off.
02 · Examples
bombs = [[0,0,2],[3,0,1],[2,0,1]]
3
Setting off bomb 0 at (0,0) reaches bomb 2 at distance 2. Bomb 2 then reaches bomb 1 at distance 1. All 3 bombs explode.
bombs = [[1,1,1],[10,10,1]]
1
The bombs are too far apart to affect each other, so at most 1 explodes.
bombs = [[0,0,1],[0,3,5],[5,0,2]]
2
Bomb 1 at (0,3) with radius 5 reaches bomb 0 (distance 3) but not bomb 2 (distance about 5.83). Bomb 0 and bomb 2 reach nothing. The best is 2.
03 · Constraints
- 011 <= bombs.length <= 100
- 02bombs[i].length == 3
- 030 <= x, y <= 105
- 041 <= r <= 105
04 · Optimal complexity
- Time
- O(n^3)
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.