Most Stones Removed with Same Row or Column
Understanding the Problem
At first this problem looks like it requires simulation: pick a removable stone, remove it, check what is removable next, and repeat. Simulating every possible removal order would be slow and hard to reason about. There is a cleaner structure underneath.
The structure is connectivity. Two stones that share a row or column are connected. Group the stones so that every stone is reachable from every other stone through a chain of shared rows and columns. From any such group, all but one stone can be removed. To see why, remove stones in reverse order of when they were added to the group, so each stone being removed still has a neighbor (its predecessor) in the same row or column. The first stone added has no predecessor, so it stays. That leaves exactly one stone per group.
So the problem reduces to: how many connected components are there? If you have n stones forming k connected components, the answer is n - k. Each connected component must keep exactly one stone, and every other stone can be removed.
Key Constraints:
1 <= stones.length <= 1000-> With n up to 1000, an O(n^2) pairwise scan is about a million operations, which runs comfortably. This is why a brute-force graph build is acceptable here.0 <= xi, yi <= 10^4-> Coordinates go up to 10,000. To index rows and columns directly in a Union Find array, the structure must cover values up to 10^4, and rows and columns need separate ID ranges.No two stones are at the same coordinate point-> No duplicate positions. Each coordinate holds at most one stone.
Approach 1: DFS (Graph Traversal)
Intuition
Build a graph where stones are nodes, and two nodes have an edge if they share a row or column. Then count the connected components with DFS.
For each stone, check every other stone to see if they share a row or column. If they do, they are neighbors. Once the adjacency list is built, run DFS from each unvisited stone to mark an entire connected component. The answer is n - numberOfComponents.
Why n - numberOfComponents? Each connected component must keep at least one stone (the last one standing with no remaining neighbor to justify its removal). So from each component of size s, you can remove s - 1 stones. Summing across all components: total removals = sum of (s_i - 1) = n - k, where k is the number of components.
Algorithm
- Build an adjacency list: for each pair of stones
(i, j), ifstones[i]andstones[j]share a row or column, add an edge between them. - Initialize a visited array of size
n. - For each unvisited stone, run DFS to mark all stones in its connected component. Increment the component count.
- Return
n - componentCount.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Building the adjacency list requires checking every pair of stones, which is O(n^2). The DFS itself visits each node and edge once, but the number of edges can be up to O(n^2).
- Space Complexity: O(n^2). The adjacency list can store up to O(n^2) edges in the worst case when many stones share rows/columns.
This approach spends O(n^2) time and space building explicit edges between stones. The next approach merges stones into groups directly with Union Find, dropping both the edge list and the O(n^2) pairwise scan.
Approach 2: Union Find (Optimal)
Intuition
Instead of connecting stones to stones, connect rows to columns. For each stone at position [r, c], union row r with column c. Row IDs and column IDs share the same integer range (row 0 and column 0 are different things), so offset every column by 10001, one past the maximum coordinate of 10^4. Now r and c + 10001 never collide.
After all stones are processed, stones that share a row or column belong to the same Union Find set. Counting the distinct sets among the rows and columns that appear in the stones gives the number of connected components, and the answer is n - numberOfComponents.
The row-column union captures the same connectivity as the stone-to-stone graph without materializing edges. Unioning row r with column c + 10001 for stone [r, c] makes the stone's row and column share a set. Two stones sharing a row both touch that row's node, so they land in one set; two stones sharing a column both touch that column's node. Chains of such shared rows and columns merge transitively through Union Find, so each final set corresponds to one connected component of stones.
Algorithm
- Create a Union Find data structure with path compression and union by rank.
- For each stone at
[r, c], unionrwithc + 10001(offset to avoid collision between row and column IDs). - Count how many unique connected components exist among the rows and columns that appear in the stones.
- Return
n - numberOfComponents.
Visualization and Code
Loading animation...
- Time Complexity: O(n * alpha(n)). We process each stone once, performing two Union Find operations. With path compression and union by rank, each operation is nearly O(1) amortized, making the total effectively O(n).
- Space Complexity: O(n). The parent and rank arrays are fixed at 20003. The seen and components sets store at most 2n entries.