LeetCode 947 - Most Stones Removed with Same Row or Column

The problem gives us a collection of stones placed on a 2D grid. Each stone occupies a unique coordinate (x, y). A stone can be removed only if there is at least one other stone that shares either the same row or the same column.

leetcodemediumhash-tabledepth-first-searchunion-findgraph-theory

LeetCode Problem 947

Difficulty: 🟡 Medium
Topics: Hash Table, Depth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem gives us a collection of stones placed on a 2D grid. Each stone occupies a unique coordinate (x, y). A stone can be removed only if there is at least one other stone that shares either the same row or the same column.

The goal is to determine the maximum number of stones that can be removed while still respecting this rule at every step.

The key observation is that a stone cannot be removed if it becomes isolated, meaning no remaining stone shares its row or column. Because of this, every connected group of stones must leave at least one stone behind.

We can think of the stones as nodes in a graph:

  • Two stones are connected if they share a row or a column.
  • Any stones reachable from one another belong to the same connected component.

Inside a connected component containing k stones, we can remove exactly k - 1 stones. One stone must remain because the final stone has no neighboring stone in the same row or column.

Therefore:

  • If there are n total stones
  • And c connected components

Then the answer is:

$\text{Answer} = n - c$

The constraints are important:

  • stones.length <= 1000
  • Coordinates are bounded by 10^4
  • No duplicate coordinates exist

Since there are at most 1000 stones, an O(n^2) comparison between stones is acceptable. This strongly suggests that graph traversal or Union-Find approaches are viable.

Several edge cases are important:

  • A single stone cannot be removed.
  • Multiple disconnected groups each require one remaining stone.
  • Stones connected indirectly through chains still belong to the same component.
  • Fully connected row or column structures can remove all but one stone.

Approaches

Brute Force Approach

A naive approach would repeatedly search for removable stones and simulate removals one by one.

At each step:

  1. Scan every stone.
  2. Check whether another stone shares its row or column.
  3. Remove one such stone.
  4. Repeat until no more removals are possible.

This works because it follows the problem rules directly. However, it is inefficient because every removal may require rescanning the entire collection of stones. In the worst case, this leads to cubic behavior.

More importantly, reasoning about which stone to remove becomes unnecessarily complicated. The process depends heavily on connectivity rather than the exact removal order.

Key Insight

The crucial observation is that stones form connected components.

If two stones share a row or column, they belong to the same connected structure. Even if two stones do not directly share a row or column, they may still be connected indirectly through intermediate stones.

For example:

[0,0] -> [0,1] -> [1,1]

The first and third stones are connected through the middle stone.

Inside any connected component:

  • We can always remove stones until only one remains.
  • Therefore, a component with size k contributes k - 1 removable stones.

This transforms the problem into:

  1. Find the number of connected components.
  2. Subtract that count from the total number of stones.

We can solve this efficiently using either:

  • Depth-First Search
  • Breadth-First Search
  • Union-Find

Here we will use Union-Find because it cleanly models connectivity.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n) Simulates removals directly
Optimal Union-Find O(n² * α(n)) O(n) Groups connected stones into components

α(n) is the inverse Ackermann function, which is effectively constant in practice.

Algorithm Walkthrough

Optimal Union-Find Algorithm

  1. Initialize a Union-Find structure where every stone starts in its own component.

Initially, each stone is disconnected, so each stone is its own parent. 2. Compare every pair of stones.

Since n <= 1000, checking all pairs is acceptable. 3. If two stones share a row or column, union them.

Two stones belong to the same connected component if:

x1 == x2 OR y1 == y2

Union-Find merges these connected groups efficiently. 4. After processing all pairs, count the number of unique roots.

Every unique root represents one connected component. 5. Compute the result.

If there are components connected groups and n total stones:

$\text{Removable Stones} = n - \text{components}$

Why it works

Each connected component must retain at least one stone. Every other stone in that component can eventually be removed because there will always exist another stone sharing a row or column until only one remains.

Union-Find correctly identifies all connected components, including indirect connections. Therefore, subtracting the number of connected components from the total number of stones gives the maximum removable stones.

Python Solution

from typing import List

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)

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

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return

            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 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 = set()

        for i in range(n):
            components.add(find(i))

        return n - len(components)

The implementation begins by initializing the Union-Find data structure.

The parent array stores the representative parent for each stone. Initially, every stone points to itself. The rank array helps keep trees shallow during union operations.

The find function performs path compression. Whenever we search for a root, we flatten the structure by directly attaching nodes to their root parent. This significantly improves efficiency.

The union function merges two connected components. Union by rank ensures the shallower tree gets attached under the deeper tree, minimizing future lookup costs.

Next, the nested loop compares every pair of stones. If two stones share a row or column, they belong to the same connected component, so we union them.

Finally, we compute the number of distinct roots. Each unique root corresponds to one connected component.

The answer is the total number of stones minus the number of components.

Go Solution

package main

func removeStones(stones [][]int) int {
	n := len(stones)

	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(x int, y int) {
		rootX := find(x)
		rootY := find(y)

		if rootX == rootY {
			return
		}

		if rank[rootX] < rank[rootY] {
			parent[rootX] = rootY
		} else if rank[rootX] > rank[rootY] {
			parent[rootY] = rootX
		} else {
			parent[rootY] = rootX
			rank[rootX]++
		}
	}

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if stones[i][0] == stones[j][0] ||
				stones[i][1] == stones[j][1] {
				union(i, j)
			}
		}
	}

	components := make(map[int]bool)

	for i := 0; i < n; i++ {
		root := find(i)
		components[root] = true
	}

	return n - len(components)
}

The Go implementation follows the same Union-Find strategy as the Python version.

A map[int]bool is used to count unique connected components because Go does not have a built-in set type.

The recursive find function performs path compression exactly like the Python version.

Since the constraints are small, integer overflow is not a concern. Go slices naturally handle the dynamic arrays needed for parent and rank.

Worked Examples

Example 1

stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

Step-by-step unions

Pair Shared Row/Column Action
[0,0] & [0,1] Same row Union
[0,0] & [1,0] Same column Union
[0,1] & [2,1] Same column Union
[1,0] & [1,2] Same row Union
[1,2] & [2,2] Same column Union
[2,1] & [2,2] Same row Union

Eventually all stones belong to one connected component.

Value Result
Total stones 6
Connected components 1
Answer 5

Example 2

stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]

Connectivity

[0,0] connected to [0,2]
[0,0] connected to [2,0]
[2,0] connected to [2,2]
[0,2] connected to [2,2]

Stone [1,1] is isolated.

Component Stones
Component 1 [0,0], [0,2], [2,0], [2,2]
Component 2 [1,1]
Value Result
Total stones 5
Components 2
Answer 3

Example 3

stones = [[0,0]]

No unions occur.

Value Result
Total stones 1
Components 1
Answer 0

Complexity Analysis

Measure Complexity Explanation
Time O(n² * α(n)) Every pair of stones is checked once
Space O(n) Parent, rank, and component storage

The dominant cost comes from comparing every pair of stones. Since there are at most 1000 stones, this results in at most about one million comparisons, which is acceptable.

Union-Find operations are nearly constant time because of path compression and union by rank.

Test Cases

sol = Solution()

assert sol.removeStones([[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]) == 5
# Large connected component

assert sol.removeStones([[0,0],[0,2],[1,1],[2,0],[2,2]]) == 3
# One isolated stone

assert sol.removeStones([[0,0]]) == 0
# Single stone cannot be removed

assert sol.removeStones([[0,0],[0,1]]) == 1
# Two stones sharing a row

assert sol.removeStones([[0,0],[1,0]]) == 1
# Two stones sharing a column

assert sol.removeStones([[0,0],[1,1]]) == 0
# Completely disconnected stones

assert sol.removeStones([[0,0],[0,1],[1,1]]) == 2
# Indirect connectivity chain

assert sol.removeStones([[0,1],[1,0],[1,1]]) == 2
# Mixed row and column connections

assert sol.removeStones([[0,0],[0,2],[2,0],[2,2]]) == 3
# Square-shaped component

assert sol.removeStones([[0,0],[1,2],[3,4],[5,6]]) == 0
# All stones isolated

assert sol.removeStones([[0,0],[0,1],[1,0],[2,2],[2,3]]) == 3
# Multiple connected components

Test Summary

Test Why
Fully connected graph Validates maximum removals
One isolated stone Ensures disconnected components handled correctly
Single stone Smallest input
Same row pair Tests row connectivity
Same column pair Tests column connectivity
No shared rows/columns Tests isolated nodes
Indirect chain Verifies transitive connectivity
Mixed connections Ensures both row and column unions work
Square component Dense connectivity case
Multiple isolated stones Ensures no invalid removals
Multiple components Confirms component counting correctness

Edge Cases

A very important edge case is a single stone. Since no other stone shares its row or column, it cannot be removed. A buggy implementation might incorrectly assume every component contributes removable stones. Our implementation correctly computes one connected component and returns 1 - 1 = 0.

Another important edge case is indirect connectivity. Two stones may not directly share a row or column but can still belong to the same connected component through intermediate stones. For example:

[0,0] -> [0,1] -> [1,1]

A naive implementation that only checks direct neighbors during removal reasoning might miss this relationship. Union-Find handles this naturally because unions propagate connectivity transitively.

A third important edge case is multiple disconnected groups. Each component must leave exactly one stone behind. If an implementation only tracks total connected stones globally, it may overcount removable stones. By explicitly counting unique component roots, the solution correctly preserves one stone per connected component.

A fourth subtle case occurs when many stones share the same row or column. This can create dense connectivity with many repeated union attempts. Without path compression and union by rank, performance may degrade significantly. The implementation avoids this issue through optimized Union-Find operations.