947. Most Stones Removed with Same Row or Column
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 <= 104- No two stones are at the same coordinate point.
Solution:
class Solution {
public int removeStones(int[][] stones) {
int n = stones.length;
UnionFind uf = new UnionFind(n);
// Populate uf by connecting stones that share the same row or column
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (
stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]
) {
uf.union(i, j);
}
}
}
return n - uf.count;
}
// Union-Find data structure for tracking connected components
private class UnionFind {
int[] parent; // Array to track the parent of each node
int count; // Number of connected components
UnionFind(int n) {
parent = new int[n];
Arrays.fill(parent, -1); // Initialize all nodes as their own parent
count = n; // Initially, each stone is its own connected component
}
// Find the root of a node with path compression
int find(int node) {
if (parent[node] == -1) {
return node;
}
return parent[node] = find(parent[node]);
}
// Union two nodes, reducing the number of connected components
void union(int n1, int n2) {
int root1 = find(n1);
int root2 = find(n2);
if (root1 == root2) {
return; // If they are already in the same component, do nothing
}
// Merge the components and reduce the count of connected components
count--;
parent[root1] = root2;
}
}
}
// TC: O(n)
// SC: O(n + 20002)
- Time complexity: O(n)
Since the size of the
parentarray is constant (20002), initializing it takes constant time.The
unionoperation is calledntimes, once for each stone. Allunionandfindoperations take O(α(20002))=O(1) time, where α is the inverse Ackermann function.Thus, the overall time complexity is O(n).
- Space complexity: O(n+20002)
The
parentarray takes a constant space of20002.The
uniqueNodesset can have at most 2⋅n elements, corresponding to all unique x and y coordinates. The space complexity of this set is O(n).Thus, the overall space complexity of the approach is O(n+20002).