Balls sit at integer points of a plane; balls[i] = [x, y]. Two balls are linked when they share a row (same y) and their x values differ by at most d, or share a column (same x) and their y values differ by at most d. Several balls may sit on the same point (they are linked to each other).
When you trigger a ball, it is absorbed, and absorption spreads: every ball linked to an absorbed ball is absorbed too, again and again. Implement
min_triggers(balls: list[list[int]], d: int) -> int
returning the fewest triggers needed to absorb every ball.
min_triggers([[0, 0], [3, 0], [3, 4], [9, 9], [9, 12]], 4) # 2
# (0,0)-(3,0) share row 0, gap 3; (3,0)-(3,4) share column 3, gap 4
# (9,9)-(9,12) share column 9, gap 3. Groups: {first three}, {last two}
min_triggers([[0, 0], [3, 0], [3, 4], [9, 9], [9, 12]], 2) # 5 (no links at all)
min_triggers([[1, 1], [1, 1]], 0) # 1
min_triggers([[0, 0], [2, 2]], 5) # 2 (diagonal balls never link)
Constraints: 0 <= len(balls) <= 100_000 (no balls need no triggers), coordinates in [-10**9, 10**9], 0 <= d <= 10**9.
Checking every pair of balls is O(n²), far too slow when many balls share a row.
Show hint
The answer is the number of connected groups. Within one row, sorted by x, a ball only needs to be joined to its neighbour in that order: if two balls further apart are within d, the balls between them chain them together anyway. Do the same per column and count groups with union-find.