Welcome to Subscribe On Youtube
947. Most Stones Removed with Same Row or Column
Description
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.
Solutions
Solution 1: Union-Find
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.
Solution 2: Union-Find (Optimized)
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.
Solution 3: DFS
This implementation uses depth-first search, followed by set. It traverses the relevant values and updates its state as each value is processed. A keyed container records values that must be found or updated efficiently. After all required states have been considered, the maintained result is returned.
-
class Solution { private int[] p; public int removeStones(int[][] stones) { int n = 10010; p = new int[n << 1]; for (int i = 0; i < p.length; ++i) { p[i] = i; } for (int[] stone : stones) { p[find(stone[0])] = find(stone[1] + n); } Set<Integer> s = new HashSet<>(); for (int[] stone : stones) { s.add(find(stone[0])); } return stones.length - s.size(); } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } // Solution 2 class UnionFind { private final int[] p; private final int[] size; public UnionFind(int n) { p = new int[n]; size = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; size[i] = 1; } } public int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } public boolean union(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) { return false; } if (size[pa] > size[pb]) { p[pb] = pa; size[pa] += size[pb]; } else { p[pa] = pb; size[pb] += size[pa]; } return true; } } class Solution { public int removeStones(int[][] stones) { int m = 10001; UnionFind uf = new UnionFind(m << 1); for (var st : stones) { uf.union(st[0], st[1] + m); } Set<Integer> s = new HashSet<>(); for (var st : stones) { s.add(uf.find(st[0])); } return stones.length - s.size(); } } -
class Solution { public: vector<int> p; int removeStones(vector<vector<int>>& stones) { int n = 10010; p.resize(n << 1); for (int i = 0; i < p.size(); ++i) p[i] = i; for (auto& stone : stones) p[find(stone[0])] = find(stone[1] + n); unordered_set<int> s; for (auto& stone : stones) s.insert(find(stone[0])); return stones.size() - s.size(); } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } }; // Solution 2 class UnionFind { public: UnionFind(int n) { p = vector<int>(n); size = vector<int>(n, 1); iota(p.begin(), p.end(), 0); } bool unite(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) { return false; } if (size[pa] > size[pb]) { p[pb] = pa; size[pa] += size[pb]; } else { p[pa] = pb; size[pb] += size[pa]; } return true; } int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } private: vector<int> p, size; }; class Solution { public: int removeStones(vector<vector<int>>& stones) { int m = 10001; UnionFind uf(m << 1); for (auto& st : stones) { uf.unite(st[0], st[1] + m); } unordered_set<int> s; for (auto& st : stones) { s.insert(uf.find(st[0])); } return stones.size() - s.size(); } }; -
class Solution: def removeStones(self, stones: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = 10010 p = list(range(n << 1)) for x, y in stones: p[find(x)] = find(y + n) s = {find(x) for x, _ in stones} return len(stones) - len(s) # Solution 2 class UnionFind: def __init__(self, n): self.p = list(range(n)) self.size = [1] * n def find(self, x): if self.p[x] != x: self.p[x] = self.find(self.p[x]) return self.p[x] def union(self, a, b): pa, pb = self.find(a), self.find(b) if pa == pb: return False if self.size[pa] > self.size[pb]: self.p[pb] = pa self.size[pa] += self.size[pb] else: self.p[pa] = pb self.size[pb] += self.size[pa] return True class Solution: def removeStones(self, stones: List[List[int]]) -> int: m = 10001 uf = UnionFind(m << 1) for x, y in stones: uf.union(x, y + m) return len(stones) - len({uf.find(x) for x, _ in stones}) -
func removeStones(stones [][]int) int { n := 10010 p := make([]int, n<<1) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, stone := range stones { p[find(stone[0])] = find(stone[1] + n) } s := make(map[int]bool) for _, stone := range stones { s[find(stone[0])] = true } return len(stones) - len(s) } // Solution 2 type unionFind struct { p, size []int } func newUnionFind(n int) *unionFind { p := make([]int, n) size := make([]int, n) for i := range p { p[i] = i size[i] = 1 } return &unionFind{p, size} } func (uf *unionFind) find(x int) int { if uf.p[x] != x { uf.p[x] = uf.find(uf.p[x]) } return uf.p[x] } func (uf *unionFind) union(a, b int) bool { pa, pb := uf.find(a), uf.find(b) if pa == pb { return false } if uf.size[pa] > uf.size[pb] { uf.p[pb] = pa uf.size[pa] += uf.size[pb] } else { uf.p[pa] = pb uf.size[pb] += uf.size[pa] } return true } func removeStones(stones [][]int) (ans int) { m := 10001 uf := newUnionFind(m << 1) for _, st := range stones { uf.union(st[0], st[1]+m) } s := map[int]bool{} for _, st := range stones { s[uf.find(st[0])] = true } return len(stones) - len(s) } -
class UnionFind { p: number[]; size: number[]; constructor(n: number) { this.p = Array.from({ length: n }, (_, i) => i); this.size = Array(n).fill(1); } find(x: number): number { if (this.p[x] !== x) { this.p[x] = this.find(this.p[x]); } return this.p[x]; } union(a: number, b: number): boolean { const [pa, pb] = [this.find(a), this.find(b)]; if (pa === pb) { return false; } if (this.size[pa] > this.size[pb]) { this.p[pb] = pa; this.size[pa] += this.size[pb]; } else { this.p[pa] = pb; this.size[pb] += this.size[pa]; } return true; } } function removeStones(stones: number[][]): number { const n = stones.length; const uf = new UnionFind(n); let ans = 0; for (let i = 0; i < n; ++i) { for (let j = 0; j < i; ++j) { if (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1]) { ans += uf.union(i, j) ? 1 : 0; } } } return ans; } // Solution 2 class UnionFind { p: number[]; size: number[]; constructor(n: number) { this.p = Array.from({ length: n }, (_, i) => i); this.size = Array(n).fill(1); } find(x: number): number { if (this.p[x] !== x) { this.p[x] = this.find(this.p[x]); } return this.p[x]; } union(a: number, b: number): boolean { const [pa, pb] = [this.find(a), this.find(b)]; if (pa === pb) { return false; } if (this.size[pa] > this.size[pb]) { this.p[pb] = pa; this.size[pa] += this.size[pb]; } else { this.p[pa] = pb; this.size[pb] += this.size[pa]; } return true; } } function removeStones(stones: number[][]): number { const m = 10001; const uf = new UnionFind(m << 1); for (const [x, y] of stones) { uf.union(x, y + m); } const s = new Set<number>(); for (const [x, _] of stones) { s.add(uf.find(x)); } return stones.length - s.size; } // Solution 3 function removeStones(stones: number[][]): number { const n = stones.length; const g: number[][] = Array.from({ length: n }, () => []); for (let i = 0; i < n; i++) { const [y, x] = stones[i]; for (let j = i + 1; j < n; j++) { if (y === stones[j][0] || x === stones[j][1]) { g[i].push(j); g[j].push(i); } } } const dfs = (i: number) => { const seen = new Set<number>(); let q = [i]; while (q.length) { const qNext: number[] = []; for (const i of q) { if (seen.has(i)) continue; seen.add(i); set.delete(i); qNext.push(...g[i]); } q = qNext; } }; const set = new Set(Array.from({ length: n }, (_, i) => i)); let ans = n; for (const i of set) { dfs(i); ans--; } return ans; } -
// Solution 3 function removeStones(stones) { const n = stones.length; const g = Array.from({ length: n }, () => []); for (let i = 0; i < n; i++) { const [y, x] = stones[i]; for (let j = i + 1; j < n; j++) { if (y === stones[j][0] || x === stones[j][1]) { g[i].push(j); g[j].push(i); } } } const dfs = i => { const seen = new Set(); let q = [i]; while (q.length) { const qNext = []; for (const i of q) { if (seen.has(i)) continue; seen.add(i); set.delete(i); qNext.push(...g[i]); } q = qNext; } }; const set = new Set(Array.from({ length: n }, (_, i) => i)); let ans = n; for (const i of set) { dfs(i); ans--; } return ans; }