FastPrep
Problem · Graph

Detonate Bombs with Chain Reactions

● MediumGoogleFULLTIMENEW GRADONSITE INTERVIEW
See Google hiring insights

You are given n bombs. Each bomb is represented as [x, y, r], where (x, y) is its location and r is its explosion radius.

If bomb i is detonated, it directly triggers every bomb j whose Euclidean distance from bomb i is at most r_i. A triggered bomb can then trigger other bombs, creating a chain reaction.

You may choose exactly one bomb as the initial detonation. Return the maximum number of bombs that can be detonated.

Examples
01 · Example 1
bombs = [[2,1,3],[6,1,4],[4,1,1]]
return = 3

Detonating the first bomb can trigger the third bomb, and the third bomb can trigger the second bomb.

02 · Example 2
bombs = [[0,0,1],[3,0,1]]
return = 1
03 · Example 3
bombs = [[0,0,10],[3,0,1],[6,0,1]]
return = 3
Constraints
  • 1 <= bombs.length <= 1000
  • bombs[i].length == 3
  • -10^5 <= x_i, y_i <= 10^5
  • 1 <= r_i <= 10^5
  • Use squared distances to avoid floating-point precision issues.
More Google problems
drafts saved locally
public int maximumDetonatedBombs(int[][] bombs) {
    // write your code here
}
bombs[[2,1,3],[6,1,4],[4,1,1]]
expected3
sign in to submit