Watch 10 video solutions for Most Stones Removed with Same Row or Column, a medium level problem involving Hash Table, Depth-First Search, Union Find. This walkthrough by take U forward has 196,563 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5 Explanation: One way to remove 5 stones is as follows: 1. Remove stone [2,2] because it shares the same row as [2,1]. 2. Remove stone [2,1] because it shares the same column as [0,1]. 3. Remove stone [1,2] because it shares the same row as [1,0]. 4. Remove stone [1,0] because it shares the same column as [0,0]. 5. Remove stone [0,1] because it shares the same row as [0,0]. Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Explanation: One way to make 3 moves is as follows: 1. Remove stone [2,2] because it shares the same row as [2,0]. 2. Remove stone [2,0] because it shares the same column as [0,0]. 3. Remove stone [0,2] because it shares the same row as [0,0]. Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
Example 3:
Input: stones = [[0,0]] Output: 0 Explanation: [0,0] is the only stone on the plane, so you cannot remove it.
Constraints:
1 <= stones.length <= 10000 <= xi, yi <= 104Problem Overview: You are given coordinates of stones on a 2D grid. A stone can be removed if another stone exists in the same row or column. The goal is to remove the maximum number of stones while leaving at least one stone in each connected group.
The key observation: stones connected by the same row or column form a connected component. Inside a component with k stones, you can remove k - 1 stones, leaving one behind. The problem reduces to counting how many connected components exist.
Approach 1: Depth First Search (DFS) Graph Traversal (Time: O(n²), Space: O(n))
Treat every stone as a node in a graph. Two nodes share an edge if they have the same row or column. Iterate through all stones and run a DFS whenever you encounter an unvisited stone. During DFS, explore every stone that shares a row or column with the current one and mark it visited. Each DFS traversal identifies one connected component. If there are c components among n stones, the answer becomes n - c. This approach directly models the problem as a graph traversal using Depth-First Search. It’s simple to reason about but requires comparing stones pairwise, which leads to O(n²) time.
Approach 2: Disjoint Set Union (Union-Find) (Time: O(n α(n)), Space: O(n))
Use Union-Find to group stones that share rows or columns. Initially each stone is its own set. Iterate over pairs of stones; if two stones share a row or column, union their sets. Union-Find efficiently merges components using path compression and union by rank. After processing all stones, count the number of unique parents (connected components). The maximum stones removable equals n - number_of_components. DSU avoids explicit graph traversal and keeps connectivity operations nearly constant time, making it scalable for larger inputs.
Recommended for interviews: Union-Find is the expected optimal solution. It shows strong understanding of connectivity problems and component merging. DFS still demonstrates the correct graph modeling insight and is often easier to implement quickly, but the DSU approach signals deeper familiarity with common interview patterns involving connected components.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth First Search (Graph Traversal) | O(n²) | O(n) | Good for understanding the graph connectivity model and quick implementation in interviews. |
| Disjoint Set Union (Union-Find) | O(n α(n)) | O(n) | Best general solution when grouping nodes into connected components efficiently. |