Most Stones Removed with Same Row or Column: Union-Find Connected Components

You are given a list of stones on a 2D plane, where each stone sits at an integer coordinate [row, col]. In one move, you can remove a stone if it shares its row or column with at least one other stone that has not been removed. Your goal is to find the maximum number of stones you can remove.

This is LeetCode 947: Most Stones Removed with Same Row or Column. It looks like a simulation problem at first, but the key realization is that it reduces to counting connected components with Union-Find.

Six stones placed on a grid. Stones sharing a row or column are connected. All six form one component, so 6 - 1 = 5 can be removed.

Why this problem matters

Most Stones Removed is one of the cleanest examples of how graph modeling turns a tricky simulation into a simple formula. Instead of figuring out which stones to remove in what order, you realize that within any connected component of stones (connected by shared rows or columns), you can always reduce down to exactly one stone. The answer is just n - number_of_components.

This insight, that the answer depends on connected components rather than the removal sequence, appears in many graph problems. Once you internalize it here, you can apply it to problems like Accounts Merge and Redundant Connection, where the structure of the connected components determines the answer.

The brute force approach

A brute force solution would simulate the removal process. At each step, scan for any stone that shares a row or column with another remaining stone, remove it, and repeat. You would try all possible removal orders and track the maximum number removed.

def removeStones_brute(stones):
    stones = [list(s) for s in stones]
    removed = 0
    changed = True
    while changed:
        changed = False
        for i in range(len(stones)):
            if stones[i] is None:
                continue
            for j in range(len(stones)):
                if i == j or stones[j] is None:
                    continue
                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                    stones[i] = None
                    removed += 1
                    changed = True
                    break
    return removed

This greedy simulation happens to produce the right answer, but reasoning about why requires the connected-component insight we are about to develop. The simulation also runs in O(n^2) per removal, leading to O(n^3) total time. We can do much better.

The key insight: connected components

Think of each stone as a node in a graph. Two stones are connected if they share a row or a column. Within any connected component, you can always remove stones one by one until only one remains. Why? Because at each step, the remaining stones in the component still share rows or columns with each other (removing a stone from a connected component of size k leaves a connected component of size k - 1, as long as k > 1).

That means the maximum number of removals for a component of size k is k - 1. Summing across all components, the total removals equal n - number_of_components.

Walking through it step by step

Let's trace Union-Find on stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]. We compare every pair of stones and union those that share a row or column.

After processing all pairs, every stone has the same root (0). There is 1 connected component. The answer is 6 - 1 = 5.

Notice the last pair, stones (2,1) and (2,2), already belonged to the same component when we tried to union them. Union-Find detected this immediately through the find operation.

The union-find solution

def removeStones(stones):
    n = len(stones)
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1

    for i in range(n):
        for j in range(i + 1, n):
            if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                union(i, j)

    components = sum(1 for i in range(n) if find(i) == i)
    return n - components

1. Initialization: Each stone starts as its own component. parent[i] = i for every stone index.

2. Pairwise comparison: For every pair of stones (i, j), check if they share a row (stones[i][0] == stones[j][0]) or a column (stones[i][1] == stones[j][1]). If so, union their components.

3. Find with path compression: The find function walks up the parent chain to the root, applying path halving along the way. This keeps the tree flat for near-constant lookup.

4. Union by rank: The shorter tree always attaches under the taller one, preventing degenerate chains.

5. Count components: After all unions, count the number of distinct roots. Each root represents one component.

6. The answer: n - components. Each component contributes size - 1 removals, and the sum of (size - 1) across all components equals n - components.

Complexity analysis

The n^2 pairwise comparison dominates. For the constraint n <= 1000, this is fast enough. For larger inputs, you could optimize by grouping stones by row and column using hash maps, reducing the number of union calls to O(n).

Building blocks

1. Union-Find for connected components

The core pattern: initialize every element as its own component, then merge components based on some relationship. After all merges, count the distinct roots.

parent = list(range(n))
rank = [0] * n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return
    if rank[rx] < rank[ry]:
        rx, ry = ry, rx
    parent[ry] = rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1

This template is the same one used in Redundant Connection (cycle detection), Accounts Merge (grouping by shared attributes), and Number of Provinces (counting friend groups). The only thing that changes is the condition that triggers a union.

2. Graph modeling on coordinates

The insight that stones sharing a row or column form edges in an implicit graph. You do not build an adjacency list. Instead, you iterate over pairs and check the shared-coordinate condition directly.

for i in range(n):
    for j in range(i + 1, n):
        if same_row(i, j) or same_col(i, j):
            union(i, j)

This "implicit graph" approach works whenever the connectivity rule is a simple predicate on pairs of elements. It avoids building explicit edge lists and keeps the code minimal.

Edge cases

• Single stone: n = 1, one component, answer is 1 - 1 = 0. Nothing to remove.
• No shared rows or columns: Every stone is isolated. Each is its own component. Answer is n - n = 0.
• All stones in one row: All share the same row, forming one component. Answer is n - 1.
• All stones at the same coordinate: This cannot happen per the problem constraints (all stones are at distinct positions).
• Large coordinate values: Rows and columns can be up to 10,000, but this does not affect the algorithm since we index by stone number, not by coordinate.
• Two separate clusters: If stones form two disconnected groups, the answer is n - 2.

Common mistakes

1. Trying to simulate removals. It is tempting to figure out which stone to remove first. The connected-component insight eliminates the need for simulation entirely. The removal order does not matter.

2. Building a graph on coordinates instead of stone indices. If you create nodes for every possible row and column value, you waste space and complicate the logic. Index your Union-Find by stone index (0 to n-1) instead.

3. Forgetting path compression. Without path compression, find can degrade to O(n) per call, making the overall algorithm O(n^3). Always include parent[x] = parent[parent[x]] in the find loop.

4. Counting components incorrectly. After all unions, you must call find(i) (not just check parent[i]) to get the true root. Without the final find, path compression may not have fully flattened the tree.

5. Off-by-one in the answer formula. The answer is n - components, not n - 1. If there are multiple disconnected groups, each group keeps one stone.

From understanding to recall

You have read through the solution and traced the Union-Find steps. The formula n - components makes sense. But will you remember to model this as a graph problem three weeks from now? Will you remember to union by stone index rather than by coordinate?

These are the details that slip away under pressure. Understanding is not the same as recall. You can bridge that gap with spaced repetition. Practice writing the Union-Find template and the pairwise comparison loop from scratch at increasing intervals. After a few rounds, you see "stones removed" and immediately think "connected components," without hesitation.

Most Stones Removed is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning these patterns individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Redundant Connection - Uses the same Union-Find template to detect cycles instead of counting components
• Accounts Merge - Another Union-Find problem where shared attributes (emails) define the edges
• Number of Islands - Connected components on a grid solved with DFS, the BFS/DFS alternative to Union-Find

CodeBricks breaks Most Stones Removed into its Union-Find building blocks and drills them individually with spaced repetition. You practice find with path compression, union by rank, and the connected-component counting pattern from scratch until they are automatic. When a graph connectivity problem shows up in your interview, you do not hesitate. You just write it.