class Solution:
def removeStones(self, stones):
parent = {}
def find(x):
if parent.setdefault(x, x) != x:
parent[x] = find(parent[x])
return parent[x]
for x, y in stones:
# Use ~y to avoid collision between x and y
parent.setdefault(x, x)
parent.setdefault(~y, ~y)
parent[find(x)] = find(~y)
roots = set(find(x) for x, y in stones)
return len(stones) - len(roots)
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
unordered_map<int, int> parent;
function<int(int)> find = [&](int x) {
if (!parent.count(x)) parent[x] = x;
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
};
for (auto& stone : stones) {
int x = stone[0], y = ~stone[1];
parent[x] = x;
parent[y] = y;
parent[find(x)] = find(y);
}
unordered_set<int> roots;
for (auto& stone : stones) {
roots.insert(find(stone[0]));
}
return stones.size() - roots.size();
}
};
class Solution {
Map<Integer, Integer> parent = new HashMap<>();
private int find(int x) {
if (!parent.containsKey(x)) parent.put(x, x);
if (parent.get(x) != x) parent.put(x, find(parent.get(x)));
return parent.get(x);
}
public int removeStones(int[][] stones) {
for (int[] stone : stones) {
int x = stone[0], y = ~stone[1];
parent.putIfAbsent(x, x);
parent.putIfAbsent(y, y);
parent.put(find(x), find(y));
}
Set<Integer> roots = new HashSet<>();
for (int[] stone : stones) {
roots.add(find(stone[0]));
}
return stones.length - roots.size();
}
}
var removeStones = function(stones) {
const parent = {};
function find(x) {
if (!(x in parent)) parent[x] = x;
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (const [x, y] of stones) {
parent[x] = x;
parent[~y] = ~y;
parent[find(x)] = find(~y);
}
const roots = new Set();
for (const [x, y] of stones) {
roots.add(find(x));
}
return stones.length - roots.size;
};
You are given a 2D grid with a number of stones, each represented by their coordinates [x, y] in the grid. A move consists of removing a stone that shares either its row or column with another stone (i.e., there is at least one other stone in the same row or column).
The task is to determine the maximum number of stones you can remove from the grid. You may not remove a stone if it is the only stone in its row and column. Each move must remove a single stone, and you cannot reuse or re-add any stones once removed.
Constraints:
[x, y].At first glance, one might try to simulate the moves: for each stone, check if it shares a row or column with another, and remove it if possible. But this approach is inefficient and complicated, especially as stones are removed and the grid changes.
Instead, let's look for a pattern: if stones are connected by rows or columns, they form connected groups or "islands". Within each group, we can always remove all stones except one (since each removal leaves at least one connection until only one stone remains). Thus, the problem reduces to counting these connected groups.
The key insight is: maximum stones removed = total stones - number of connected components. The challenge then becomes efficiently finding these groups.
To do this, we can use a Union-Find (Disjoint Set Union, DSU) data structure to group stones that are connected via rows or columns. This avoids brute-force and leverages efficient data structures for grouping.
number of stones - number of groups, since in each group we can remove all stones except one.
Why use ~y (bitwise NOT) for columns? Since both x and y can be in the same range, we use ~y to create a unique identifier for columns, ensuring rows and columns do not overlap in the Union-Find structure.
[x, y]:
x (row) and ~y (column).x (rows) and ~y (columns) used.number of stones - number of unique roots.
Example Input: [[0,0],[0,1],[1,0],[1,2],[2,2],[2,3]]
Step-by-step, each stone is unioned with its row and column, grouping them. At the end, all stones are part of one group, so we can remove all but one.
O(N^2) per move, and potentially exponential overall as the configuration changes.
O(1) due to path compression and union by rank (amortized).2N operations (one for each row and column per stone).O(N * α(N)), where α is the inverse Ackermann function (very slow-growing, so nearly linear).O(N) for parent mappings.Thus, the optimized solution is efficient and suitable for large inputs.
The "Most Stones Removed with Same Row or Column" problem is elegantly solved by recognizing that the problem reduces to finding connected groups of stones. Using Union-Find, we efficiently group stones sharing rows or columns, and count the number of groups. The maximum stones we can remove is simply the total stones minus the number of groups. This approach is both efficient and conceptually clean, leveraging classic data structures to transform a seemingly complex simulation into a simple counting problem.