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 <= 104This 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.
C++
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.
Java
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.
| 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. |
G-53. Most Stones Removed with Same Row or Column - DSU • take U forward • 133,414 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 FleetCodePractice this problem
Open in Editor