STEP 15 · GRAPHS · UNION COORDINATES, NOT STONES · MEDIUM

Most Stones Removed With Same Row or Column

WHAT IT SAYS

A stone is removable if another stone shares its row or column; maximise removals from a set of stones on a grid.

WHAT IT'S REALLY ASKING

"Chase the removal ORDER and you drown; chase what removal can never do and the problem opens: within a group of stones chained by shared rows/columns, you can always peel down to exactly ONE survivor — and never zero. So the answer is stones minus groups, and the groups are connected components. The twist that makes it elegant: union each stone's ROW with its COLUMN, and the stones themselves vanish from the data structure."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Simulate removals with lookahead

Exponential with backtracking; greedy variants are order-sensitive traps

Repeatedly pick a stone that currently shares a row or column with another, remove it, update the shared-line counts, and recurse or greedily continue — backtracking if a choice strands stones that could have been removed under a different order.

WHERE THE WORK IS WASTED — The simulation sweats over ordering — remove the wrong stone first and its lonely partner is stranded — but the FINAL COUNT is order-invariant, which the simulation never learns: every maximal chained group collapses to exactly one stone regardless of the peeling sequence (peel leaves of any spanning structure inward), and no sequence does better (the last stone of a group has, by definition, no partner left). Searching over orders to optimise an order-invariant quantity is the same sin as planning interchangeable cable moves: the answer was arithmetic — total minus groups — before the first removal was ever simulated.

KEY OBSERVATION — THE UNLOCKlink

Each component keeps exactly one stone. Rows can be nodes.

First the count. Define stones connected when they share a row or column, extended transitively; the groups are this relation's connected components. Claim: a component of size s yields exactly s−1 removals. Achievability: take any spanning tree of the component's share-a-line graph and delete leaves inward — every leaf, at its moment of deletion, still shares a line with its tree-parent, so every deletion is legal, and s−1 deletions leave the root. Upper bound: removals never merge components (deleting a stone only removes chains), and a component's final stone has no partner — one survivor per component is a floor. So: answer = total stones − number of components. The entire problem is now 'count components', and the interesting part becomes HOW. Stone-to-stone unioning works but costs O(n²) pair checks — every pair interrogated for a shared coordinate. The reframe that kills the quadratic: stop treating stones as nodes. Let the NODES be the coordinate lines themselves — row r as one node, column c as another (offset column ids by a constant, or hash, to keep the namespaces disjoint) — and let each stone be an EDGE joining its row-node to its column-node. Two stones sharing a row are then edges incident to the same row-node: connected through it in one hop, no pairwise check ever performed. Transitive stone-chains become ordinary path-connectivity in the line-graph, and each stone contributes exactly one union operation: O(n α) total. One bookkeeping consequence of dissolving the stones: 'number of stone-components' must be counted as the number of distinct ROOTS among lines that actually appear (touched by at least one stone) — untouched rows and columns are phantom singletons that must not inflate the count. A set of find-roots over the stones' own coordinates, sized at the end, does it. Name the general move, because it recurs: when 'connected' means 'share an attribute', union elements THROUGH their attributes — attribute-nodes act as hubs, converting all-pairs comparisons into per-element registrations. Accounts Merge does the identical thing with emails as the hubs.

DSU over row/column nodes, stones as unions

O(n · α) time past hashing, O(rows + cols) DSU space touched

For each stone (r, c): union(node(r), node(offset + c)) — using a hash-map DSU or an offset of 1e5. Then collect find(node(r)) for every stone into a set; components = set size; return stones − components.

WHAT YOU TRADED — The line-node reframe wins asymptotically but abstracts the stones away — recovering WHICH stones to remove, or an actual removal order, requires rebuilding per-component structure (any spanning-tree leaf order works) that the count alone never materialised; stone-to-stone unioning keeps stones addressable at quadratic cost. The transferable lesson is twofold: order-invariant outcomes turn sequencing problems into counting problems (survivors = components), and shared-attribute connectivity should union THROUGH the attributes — hubs replace pairwise comparison, the same economy as bucketing.

WATCH THE IDEA RUN

●

union-find nodes rows & columns, not stones

stones 6

removable = stones − components …

A stone can be removed if it shares a row or column with a survivor. Play the removals out and you drown in ordering questions: which stone first, does it matter, could a greedy strand someone?

step 1 / 9

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Attributes as Union Hubs

YOU'LL SEE IT AGAIN WHEN

Connectivity is defined by SHARING an attribute (row, column, email, prime factor) — pairwise checks would be quadratic re-derivations of hub membership.
The asked-for quantity is order-invariant (survivors, groups, parity) though the problem narrates a sequence of operations.
Component counting must range over attributes that APPEAR — phantom untouched attributes would inflate the tally.

SAME BLUEPRINT, DIFFERENT PROBLEM

Accounts Merge (emails as the hubs, verbatim)Number of Provinces (the component count in its plainest form)Smallest String With Swaps (positions unioned through swap pairs)Groups of Special-Equivalent Strings

The bar isn't "solved it once." It's "could rebuild it from the observation."