Minimum triggers to clear linked balls on a grid

Model the balls as a graph. Each ball is a node. Two balls share an edge when they sit on the same row or the same column and are at most d apart along that line. Triggering one ball absorbs every ball you can reach from it by following edges, so one trigger clears exactly one connected component. The minimum number of triggers is the number of connected components. Pick any one ball per component and you are done. Fewer is impossible, because no trigger can cross between components.

Brute force. Compare every pair of balls, add an edge when they qualify, then count components with BFS or union-find. This is O(n²) in time and can use O(n²) memory for the edges. It is a fine opening when n is a few thousand, but it is too slow at n = 10⁵.

Optimal: only neighbours along a line matter. Group the balls by x (columns). Sort each column by y. Suppose three balls sit in one column with a < b < c, and c - a <= d. Then b - a <= d and c - b <= d both hold too. So within a sorted line, linking each ball only to the next ball, when their gap is <= d, gives the same components as linking every qualifying pair. Do the same for rows: group by y and sort by x. Merge each linked pair with union-find. That gives at most 2n union calls after an O(n log n) sort.

Invariants:

• After we process a line, any two balls in the same run (all gaps <= d) are in one set.
• A union never merges balls that are not connected. Each union comes from a real edge.
• Duplicate coordinates have gap 0, so they always merge. That matches "distance at most d".

The answer is the number of distinct roots. Return one representative per component if the interviewer wants the actual balls to trigger.

from collections import defaultdict
from typing import Dict, List, Tuple


class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1


def _link_lines(
    balls: List[List[int]], dsu: DSU, d: int, key_axis: int
) -> None:
    """Group balls by balls[i][key_axis]; link sorted neighbours within d."""
    other = 1 - key_axis
    lines: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
    for i, ball in enumerate(balls):
        lines[ball[key_axis]].append((ball[other], i))
    for line in lines.values():
        line.sort()
        for (p, i), (q, j) in zip(line, line[1:]):
            if q - p <= d:
                dsu.union(i, j)


def min_triggers(balls: List[List[int]], d: int) -> int:
    """Minimum number of balls to trigger so that every ball is absorbed."""
    if d < 0:
        raise ValueError("d must be non-negative")
    dsu = DSU(len(balls))
    _link_lines(balls, dsu, d, key_axis=0)  # same x: a column, compare y
    _link_lines(balls, dsu, d, key_axis=1)  # same y: a row, compare x
    return dsu.components


def triggers_to_press(balls: List[List[int]], d: int) -> List[int]:
    """One ball index per component: a valid minimum set of triggers."""
    dsu = DSU(len(balls))
    _link_lines(balls, dsu, d, key_axis=0)
    _link_lines(balls, dsu, d, key_axis=1)
    chosen: Dict[int, int] = {}
    for i in range(len(balls)):
        chosen.setdefault(dsu.find(i), i)
    return sorted(chosen.values())


if __name__ == "__main__":
    assert min_triggers([], 3) == 0
    assert min_triggers([[5, 5]], 0) == 1
    # Chain across a column and a row: (0,0)-(0,2)-(3,2)
    assert min_triggers([[0, 0], [0, 2], [3, 2], [9, 9]], 3) == 2
    # Gap too large: d = 2, so (0,2)-(3,2) no longer link
    assert min_triggers([[0, 0], [0, 2], [3, 2], [9, 9]], 2) == 3
    # Diagonal neighbours never connect
    assert min_triggers([[0, 0], [1, 1]], 10) == 2
    # Duplicates merge even with d = 0
    assert min_triggers([[2, 2], [2, 2], [2, 3]], 0) == 2
    # Bridge through the middle ball: 0 and 8 are 8 apart, but 4 links both
    assert min_triggers([[0, 0], [0, 4], [0, 8]], 4) == 1
    assert triggers_to_press([[0, 0], [0, 2], [3, 2], [9, 9]], 3) == [0, 3]
    print("ok")

• Grouping: O(n) time and O(n) space.
• Sorting each line: O(n log n) in total. Every ball appears in exactly one column and one row.
• Unions: at most 2(n - 1) calls. Each costs O(α(n)) amortized with path halving and union by size.
• Total: O(n log n) time, O(n) space. The brute force is O(n²) time.

• balls = [], d = 3 gives 0.
• balls = [[5,5]], d = 0 gives 1.
• balls = [[0,0],[0,2],[3,2],[9,9]], d = 3 gives 2. The first three chain through column 0 and then row 2. (9,9) stands alone.
• The same balls with d = 2 give 3. The row gap of 3 is now too large.
• balls = [[0,0],[1,1]], d = 10 gives 2. Diagonal balls never connect, however close they are.
• balls = [[2,2],[2,2],[2,3]], d = 0 gives 2. The duplicates merge (distance 0). (2,3) is 1 away and does not.
• balls = [[0,0],[0,4],[0,8]], d = 4 gives 1. The ends are 8 apart but chain through the middle ball.
• Large coordinates, such as [[-10**9, 0], [10**9, 0]] with d = 2*10**9, give 1. Python has no overflow, but call out long in Java or C++.
• A 300×300 grid of balls with spacing 1 and d = 1 gives 1. This is a performance check with 90k balls.

1. Return which balls to trigger. Pick one root per component, as triggers_to_press does. If there is a tie-break rule, such as the lowest index or the leftmost ball, keep the best member per root while scanning.
2. Each ball has its own blast radius r_i. Now ball i absorbs j when j is on the same line within r_i. The edges become directed, so the answer is the number of source SCCs in the condensation, not the number of components. Build edges per line with a sorted array and binary search (or a sweep with a monotonic stack to cut edges), run Tarjan or Kosaraju, then count SCCs with in-degree 0.
3. Streaming inserts. Balls arrive one at a time, and you report the trigger count after each one. Keep a sorted container per row and per column (for example SortedList). On insert, find the predecessor and successor on both lines and union with each one within d. That is O(log n) per insert plus α(n). Deletions break union-find. Answer offline with a segment tree over time plus a rollback DSU, or rebuild the affected components.
4. Also connect along diagonals, or use Euclidean distance. For diagonals, add two more groupings keyed on x - y and x + y. For a Euclidean radius, bucket the balls into grid cells of side d and compare only the 3×3 neighbouring cells, which takes about O(n) expected time.
5. Distributed or very large n. Shard by column, then by row. Each shard emits local union pairs, and a final pass merges them in one DSU. The sort-by-line step parallelizes naturally.

Mid-level (L4)

• Recognises that the answer is the number of connected components, and explains why one trigger per component is enough and also necessary.
• Gets the O(n²) pairwise version working with BFS or union-find. Handles empty input and duplicates.
• With a hint, sees that sorting each line and linking adjacent balls is enough.

Senior (L5)

• Reaches the O(n log n) sort-and-link solution without help, and argues why adjacent links preserve connectivity.
• Writes a clean DSU with path compression and union by size, and states its amortized cost.
• Tests the edge cases unprompted: diagonal balls, d = 0, a chain bridging far-apart balls, and large coordinates.

Staff (L6+)

• Handles follow-ups 2 and 3 fluently: knows that a per-ball radius makes the graph directed and needs SCC sources, and that deletions need offline or rollback techniques.
• Discusses trade-offs, such as memory for the explicit edge lists versus implicit linking, and spatial hashing for the Euclidean variant.
• Ties the problem back to real systems: cluster detection on geo points (for example nearby drivers or pickups) and sharding union-find.