FastPrep
Problem · Graph

Detonate Bombs with Chain Reactions

Learn this problem
● MediumGoogleFULLTIMENEW GRADONSITE INTERVIEW
See Google hiring insights

Problem statement

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.

Function

maximumDetonatedBombs(bombs: int[][]) → int

Examples

Example 1

bombs = [[2,1,3],[6,1,4],[4,1,1]]return = 3

Detonating the second bomb triggers both other bombs directly, so all three bombs detonate.

Example 2

bombs = [[0,0,1],[3,0,1]]return = 1

Example 3

bombs = [[0,0,10],[3,0,1],[6,0,1]]return = 3

Constraints

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • -10^5 <= x_i, y_i <= 10^5
  • 1 <= r_i <= 10^5
  • Use 64-bit squared distances to avoid overflow and 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
checking account