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
-
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]; } } -
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]; } }; -
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) -
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) } -
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; }