LeetCode 947: Most Stones Removed with Same Row or Column
Problem Description
Explanation:
The problem can be solved using a Union Find (Disjoint Set Union) data structure. We treat stones as nodes in a graph, where stones in the same row or column are connected. By finding connected components, we can determine the maximum number of stones that can be removed.
- Create a Union Find data structure with each stone as a node.
- For each stone pair, if they share the same row or column, union their components.
- The maximum number of stones that can be removed is the total number of stones minus the number of connected components.
Time Complexity: O(n * α(n)) where α is the inverse Ackermann function (almost constant). Space Complexity: O(n)
:
Solutions
class Solution {
public int removeStones(int[][] stones) {
int n = stones.length;
UnionFind uf = new UnionFind(n);
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.getNumOfComponents();
}
class UnionFind {
int[] parent;
int components;
public UnionFind(int n) {
parent = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
components--;
}
}
public int getNumOfComponents() {
return components;
}
}
}Related LeetCode Problems
Loading editor...