Course4all
Join us on telegram
Home/dsa/Union Find/Most Stones Removed

Most Stones Removed

Master this topic with zero to advance depth.

Most Stones Removed

On a 2D plane, return the largest number of stones that can be removed. A stone can be removed if it shares a row or column with another stone.

Medium

Examples

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

Level I: DFS (Component Counting)

Intuition

Represent stones as nodes and connect them if they share a row/column. Total stones - Number of components = Max stones removed.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

6 stones. DFS finds 1 connected component. 6 - 1 = 5.

java
import java.util.*;
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length; List<Integer>[] adj = new ArrayList[n]; for(int i=0; i<n; i++) adj[i]=new ArrayList<>();
        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]) { adj[i].add(j); adj[j].add(i); }
        boolean[] vis = new boolean[n]; int comps = 0;
        for(int i=0; i<n; i++) if(!vis[i]) { comps++; dfs(adj, vis, i); }
        return n - comps;
    }
    private void dfs(List<Integer>[] adj, boolean[] v, int u) { v[u]=true; for(int next:adj[u]) if(!v[next]) dfs(adj, v, next); }
}
Approach 2

Level III: Union-Find (Row-Column Mapping)

Intuition

Treat rows and columns as nodes. For each stone (r, c), union row r with column c. The number of stones removed is (Total Stones - Number of components).

⏱ O(N \cdot \alpha(N))💾 O(Range)

Detailed Dry Run

Stone (0, 0): Union row 0 with column 10001 (offset to distinguish).

java
import java.util.*;
class Solution {
    Map<Integer, Integer> p = new HashMap<>(); int count = 0;
    public int removeStones(int[][] stones) {
        for (int[] s : stones) union(s[0], s[1] + 10001);
        return stones.length - count;
    }
    private int find(int i) {
        if (p.putIfAbsent(i, i) == null) count++;
        if (p.get(i) != i) p.put(i, find(p.get(i)));
        return p.get(i);
    }
    private void union(int i, int j) { int r1 = find(i), r2 = find(j); if (r1 != r2) { p.put(r1, r2); count--; } }
}
← Previous QuestionSatisfiability of Equality Equations
Next Question →Smallest String With Swaps