Most Stones Removed with Same Row or Column Medium 0 attempts
LeetCode ↗

Most Stones Removed with Same Row or Column

Medium GraphBFSDFS LeetCode

Given stones on a 2D plane, remove a stone if it shares a row or column with another. Return max stones removable.

Example: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] → Output: 5

Sample Input
—
Sample Output
—
Constraints
  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 10^4
Test Cases
Case 1
Args: [[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]] Expected: 5
Topics
GraphBFSDFS

Union-Find (Count Components)

Max removable = total stones - number of connected components.

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, ~c);
  const roots = new Set();
  for (const [r] of stones) roots.add(find(r));
  return stones.length - roots.size;
}

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

Saved in this browser only. Private to you.

JavaScript