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.
This approach models the problem as a graph problem, where each stone can be a vertex and there is an edge between two vertices if the stones share the same row or column. We can perform a DFS to count the number of connected components. The maximum number of stones that can be removed from each connected component is the size of the component minus one.
The code uses DFS to explore each cluster of stones by recursively visiting every stone that shares a row or column with the current stone. The graph is constructed where each stone's coordinates map to a list of other stones it is directly connected to (either via the same row or column). By counting the number of unique connected components (rooted at stones we start a DFS on), we subtract the number of components from total stones to get the maximum removable stones.
Time Complexity: O(N^2) where N is the number of stones, due to the pairwise comparison to build the graph. Space Complexity: O(N), due to the space needed for the graph and visited tracking.
This approach models the problem using the Union-Find data structure to group stones that belong to the same connected component. By unioning stones that share the same row or column, we can determine the number of connected components and calculate the maximum number of removable stones by reducing the total number of components from the total stones.
The code utilizes a Union-Find to manage the connections between stones by mapping an x-coordinate as is, and applying ~ to the y-coordinate to separate row and column spaces uniquely. The solution of maximum removable stones results from the difference between the total stones and the number of unique components.
Time Complexity: O(N) average time complexity due to efficient union-find operations. Space Complexity: O(N) for the storage of parent pointers in the union-find structure.
We can use a union-find data structure to maintain the relationships between stones. If two stones are in the same row or column, we consider them to be connected and use the union-find to link them together. In the end, we count how many connected components there are in the union-find, which corresponds to the number of stones that can remain. Therefore, the total number of stones that can be removed is the total number of stones minus the number of stones that can remain. We can also record the number of successful unions during the merge process, which equals the number of stones that can be removed.
The time complexity is O(n^2 times \alpha(n)), and the space complexity is O(n). Here, n is the number of stones.
Python
Java
C++
Go
TypeScript
We can add an offset to the y-coordinates of the stones, allowing us to unify the x-coordinates and y-coordinates. Then, we use a union-find data structure to maintain the relationship between x-coordinates and y-coordinates.
We iterate through each stone, merging its x-coordinate with its y-coordinate.
Finally, we iterate through all the stones again, putting the root node of each stone's x-coordinate into a set. The number of elements in this set represents the number of stones that can remain. Therefore, the total number of stones that can be removed is the total number of stones minus the number of stones that can remain.
The time complexity is O(n times \alpha(m)), and the space complexity is O(m). Here, n and m represent the number of stones and the maximum value of the coordinates, respectively.
Python
Java
C++
Go
TypeScript
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach using Depth First Search (DFS) | Time Complexity: O(N^2) where N is the number of stones, due to the pairwise comparison to build the graph. Space Complexity: O(N), due to the space needed for the graph and visited tracking. |
| Approach using Disjoint Set Union (Union-Find) | Time Complexity: O(N) average time complexity due to efficient union-find operations. Space Complexity: O(N) for the storage of parent pointers in the union-find structure. |
| Union-Find | — |
| Union-Find (Optimized) | — |
| DFS | — |
| 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. |
G-53. Most Stones Removed with Same Row or Column - DSU • take U forward • 196,563 views views
Watch 9 more video solutions →Practice Most Stones Removed with Same Row or Column with our built-in code editor and test cases.
Practice on FleetCode