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

Most Stones Removed with Same Row or Column

Medium GraphBFSDFS LeetCode

You're given a list of stones placed on a 2D grid, each described by its [x, y] coordinates. A stone can be removed as long as some other remaining stone still shares its row or its column. Determine the largest number of stones that can be removed this way.

Input Format
Implement removeStones(stones). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output
5

Example 2

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

Union-Find (Count Components)

Max removable = total stones - number of connected components.

javascript
function removeStones(stones) {
  const parent = new Map(), size = new Map();
  function find(x) { if(!parent.has(x)){parent.set(x,x);size.set(x,1);}let root=x;while(parent.get(root)!==root)root=parent.get(root);while(parent.get(x)!==x){const next=parent.get(x);parent.set(x,root);x=next;}return root; }
  function union(a, b) { a=find(a);b=find(b);if(a===b)return;if(size.get(a)<size.get(b))[a,b]=[b,a];parent.set(b,a);size.set(a,size.get(a)+size.get(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