FastPrepFastPrep
Problem Brief

Detonate Bombs with Chain Reactions

FULLTIMENEW GRADONSITE INTERVIEW
See Google online assessment and 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.

1Example 1

Input
bombs = [[2,1,3],[6,1,4],[4,1,1]]
Output
3
Explanation

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

2Example 2

Input
bombs = [[0,0,1],[3,0,1]]
Output
1

3Example 3

Input
bombs = [[0,0,10],[3,0,1],[6,0,1]]
Output
3

Constraints

Limits and guarantees your solution can rely on.

  • 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.
public int maximumDetonatedBombs(int[][] bombs) {
    // write your code here
}
Input

bombs

[[2,1,3],[6,1,4],[4,1,1]]

Output

3

Sign in to submit your solution.