Medium · Graphs

Detonate the Maximum Bombs

Given bombs where bombs[i] = [xi, yi, ri] is a bomb centered at (xi, yi) with blast radius ri, return the maximum number of bombs you can detonate by setting off exactly one of them. Detonating a bomb also detonates every bomb whose center lies within its radius, and those bombs detonate others in turn.

Examples

Example 1

{
  "bombs": [
    [10, 10, 5],
    [13, 13, 5],
    [16, 16, 5],
    [19, 19, 5],
    [40, 40, 1]
  ]
}

Output: max 4

Example 2

{
  "bombs": [
    [0, 0, 6],
    [4, 0, 1],
    [0, 4, 1],
    [20, 20, 1]
  ]
}

Output: max 3

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.