Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/947.html
947. Most Stones Removed with Same Row or Column (Medium)
On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
What is the largest possible number of moves we can make?
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Example 3:
Input: stones = [[0,0]]
Output: 0
Note:
1 <= stones.length <= 10000 <= stones[i][j] < 10000
Related Topics:
Depth-first Search, Union Find
Solution 1. DFS Iterative
Let’s call stone A and B are neighbors if they are in the same row/column.
Define a component as a set of stones where each of them are neighbors and none of them is neighbor of stones outside of this set.
For each component, we can always remove the stones until there is just one left.
So we use DFS to visit the stones in the same component, and each component can contribute conponentSize - 1 moves.
// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
// Time: O(N^2)
// Space: O(N^2)
// Ref: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solution/
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int N = stones.size();
vector<vector<int>> graph(N, vector<int>(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]) {
graph[i][++graph[i][0]] = j;
graph[j][++graph[j][0]] = i;
}
}
}
int ans = 0;
vector<bool> seen(N);
for (int i = 0; i < N; ++i) {
if (seen[i]) continue;
stack<int> s;
s.push(i);
seen[i] = true;
--ans;
while (s.size()) {
int node = s.top();
s.pop();
++ans;
for (int j = 1; j <= graph[node][0]; ++j) {
int n = graph[node][j];
if (!seen[n]) {
s.push(n);
seen[n] = true;
}
}
}
}
return ans;
}
};
Solution 2. DFS Recursive
// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
void dfs(vector<vector<int>> &G, vector<bool> &visited, int start) {
visited[start] = true;
for (int n : G[start]) {
if (visited[n]) continue;
dfs(G, visited, n);
}
}
int getComponentCount(vector<vector<int>> &G) {
vector<bool> visited(G.size());
int ans = 0;
for (int i = 0; i < G.size(); ++i) {
if (visited[i]) continue;
++ans;
dfs(G, visited, i);
}
return ans;
}
public:
int removeStones(vector<vector<int>>& stones) {
int N = stones.size();
vector<vector<int>> G(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
return stones.size() - getComponentCount(G);
}
};
Solution 3. BFS
// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
void bfs(vector<vector<int>> &G, vector<bool> &visited, int start) {
visited[start] = true;
queue<int> q;
q.push(start);
while (q.size()) {
int u = q.front();
q.pop();
for (int v : G[u]) {
if (visited[v]) continue;
visited[v] = true;
q.push(v);
}
}
}
int getComponentCount(vector<vector<int>> &G) {
int ans = 0;
vector<bool> visited(G.size());
for (int i = 0; i < G.size(); ++i) {
if (visited[i]) continue;
++ans;
bfs(G, visited, i);
}
return ans;
}
public:
int removeStones(vector<vector<int>>& stones) {
int N = stones.size();
vector<vector<int>> G(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
return stones.size() - getComponentCount(G);
}
};
Solution 4. Union Find
// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
// Time: O(N^2)
// Space: O(N)
class UnionFind {
vector<int> id, rank;
int cnt;
public:
UnionFind(int n) : cnt(n), id(n), rank(n, 1) {
for (int i = 0; i < n; ++i) id[i] = i;
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
if (rank[x] <= rank[y]) {
id[x] = y;
if (rank[x] == rank[y]) rank[y]++;
} else id[y] = x;
--cnt;
}
int getCount() { return cnt; }
};
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int N = stones.size();
UnionFind uf(N);
for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
uf.connect(i, j);
}
}
}
return stones.size() - uf.getCount();
}
};
-
class Solution { public int removeStones(int[][] stones) { int length = stones.length; if (length <= 1) return 0; int[] parents = new int[20000]; for (int i = 0; i < 20000; i++) parents[i] = i; for (int[] stone : stones) union(parents, stone[0], stone[1] + 10000); Set<Integer> set = new HashSet<Integer>(); for (int[] stone : stones) set.add(findAncestor(parents, stone[0])); return length - set.size(); } public void union(int[] parents, int row, int column) { int rowParent = findAncestor(parents, row), columnParent = findAncestor(parents, column); if (rowParent != columnParent) parents[rowParent] = columnParent; } public int findAncestor(int[] parents, int start) { int ancestor = start; int cur = start; while (ancestor != parents[ancestor]) ancestor = parents[ancestor]; while (cur != parents[cur]) { int curParent = parents[cur]; parents[cur] = ancestor; cur = curParent; } return ancestor; } } ############ 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]; } } -
// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/ // Time: O(N^2) // Space: O(N^2) // Ref: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solution/ class Solution { public: int removeStones(vector<vector<int>>& stones) { int N = stones.size(); vector<vector<int>> graph(N, vector<int>(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]) { graph[i][++graph[i][0]] = j; graph[j][++graph[j][0]] = i; } } } int ans = 0; vector<bool> seen(N); for (int i = 0; i < N; ++i) { if (seen[i]) continue; stack<int> s; s.push(i); seen[i] = true; --ans; while (s.size()) { int node = s.top(); s.pop(); ++ans; for (int j = 1; j <= graph[node][0]; ++j) { int n = graph[node][j]; if (!seen[n]) { s.push(n); seen[n] = true; } } } } return ans; } }; -
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) ############ class Solution(object): def removeStones(self, stones): """ :type stones: List[List[int]] :rtype: int """ N = len(stones) self.map = [-1] * N for i in range(N): for j in range(i + 1, N): if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]: self.union(i, j) res = N print(self.map) for i in range(N): if self.map[i] == -1: res -= 1 return res def find(self, x): return x if self.map[x] == -1 else self.find(self.map[x]) def union(self, x, y): fx = self.find(x) fy = self.find(y) if fx != fy: self.map[fx] = fy -
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) }