Most Stones Removed with Same Row or Column

medium graph union find dfs hash map

Problem

Stones sit on a 2D plane; you may remove a stone iff another stone shares its row or column. Return the maximum stones removable.

Inputstones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

Output5

Connected components by shared row/col give answer = stones − components.

stones (r-c, comma list)

def removeStones(stones):
    parent = {}
    def find(x):
        parent.setdefault(x, x)
        if parent[x] != x: parent[x] = find(parent[x])
        return parent[x]
    def union(a, b):
        parent[find(a)] = find(b)
    for r, c in stones:
        union(("r", r), ("c", c))
    roots = {find(("r", r)) for r, c in stones}
    return len(stones) - len(roots)

function removeStones(stones) {
  const parent = new Map();
  function find(x) {
    if (!parent.has(x)) parent.set(x, x);
    if (parent.get(x) !== x) parent.set(x, find(parent.get(x)));
    return parent.get(x);
  }
  function union(a, b) { parent.set(find(a), find(b)); }
  for (const [r, c] of stones) union("r" + r, "c" + c);
  const roots = new Set();
  for (const [r] of stones) roots.add(find("r" + r));
  return stones.length - roots.size;
}

class Solution {
    Map<Integer, Integer> parent = new HashMap<>();
    public int removeStones(int[][] stones) {
        for (int[] s : stones) union(s[0], s[1] + 10000);
        Set<Integer> roots = new HashSet<>();
        for (int[] s : stones) roots.add(find(s[0]));
        return stones.length - roots.size();
    }
    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); }
    void union(int a, int b) { parent.put(find(a), find(b)); }
}

unordered_map<int, int> parent;
int find(int x) { if (!parent.count(x)) parent[x] = x; if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
void unite(int a, int b) { parent[find(a)] = find(b); }
int removeStones(vector<vector<int>>& stones) {
    parent.clear();
    for (auto& s : stones) unite(s[0], s[1] + 10000);
    unordered_set<int> roots;
    for (auto& s : stones) roots.insert(find(s[0]));
    return (int)stones.size() - (int)roots.size();
}

Explanation

The neat realization is that any group of stones connected through shared rows and columns can be shrunk down until only one stone is left. So from each connected group of size k you can remove k - 1 stones. Add that up and the answer is simply total stones − number of groups.

To find the groups we use union-find. The trick is what we union: instead of linking stones to stones, each stone unions its row label with its column label. In the code that's union(("r", r), ("c", c)). Two stones that share a row (or a column) end up tied to the same row/column label, so they automatically land in the same group.

The find function returns the representative root of a label, with path compression (parent[x] = find(parent[x])) to keep it fast. After unioning every stone, we collect the distinct roots of all the stones' row labels — that count is the number of connected groups.

Finally we return len(stones) - len(roots).

Example: [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] all link into a single group, so groups = 1 and the answer is 6 - 1 = 5.

Time: O(n α(n)) Space: O(n)