Problem

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

Examples

Example 1:

$$ \begin{matrix} \colorbox{lightgrey} S & \colorbox{lightgrey}S & \\ \colorbox{lightgrey} S & & \colorbox{lightgrey} S \\ & \colorbox{lightgrey} S & \colorbox{lightgrey} S \\ \end{matrix} $$

graph TD
	A([0,0]) --- B([0,1])
	A([0,0]) --- C([1,0])
	B([0,1]) --- F([2,1])
	C([1,0]) --- E([1,2])
	D([2,2]) --- E([1,2])
	D([2,2]) --- F([2,1])
  
1
2
3
4
5
6
7
8
9

Input: stones =[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.

Example 2:

$$ \begin{matrix} \colorbox{lightgrey} S & & \colorbox{lightgrey} S \\ & \colorbox{lightgrey} S & \\ \colorbox{lightgrey} S & & \colorbox{lightgrey} S \\ \end{matrix} $$

graph TD
	A([0,0]) --- B([0,2])
	A([0,0]) --- D([2,0])
	B([0,2]) --- E([2,2])
	C([1,1])
	D([2,0]) --- E([2,2])
  
1
2
3
4
5
6
7

Input: stones =[[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to make 3 moves is as follows:
1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

Example 3:

1
2
3

Input: stones =[[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

Similar Questions

This is very similar to Number of Islands.

Solution

Method 1 - Checking connectivity with DFS

Video Explanation

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int removeStones(int[][] stones) {
        Set<int[]> visited = new HashSet();
        int numIslands = 0;
        for (int[] u : stones){
            if (!visited.contains(u)){
               dfs(u, visited, stones); 
               numIslands++;
            }
        }
        return stones.length - numIslands;
    }
    
    private void dfs(int[] u, Set<int[]> visited, int[][] stones){
        visited.add(u);
        for (int[] v: stones){
            if (!visited.contains(v)){
				// stone with same row or column. group them into island
                if (u[0] == v[0] || u[1] == v[1]) {
                    dfs(v, visited, stones);
                }
            }
        }
    }
}

Complexity

  • Time: O(n^2), where n is number of stones
  • Space: O(n) assuming visited set and recursion stack

Method 2 - Checking connectivity with DFS with explicit graph

Here’s a detailed solution using DFS:

  1. Build the Graph: We need to connect stones that share the same row or column.
  2. Find Connected Components: We use DFS to traverse connected stones.
  3. Count Removable Stones: For each connected component, we can remove all stones except one.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();

        // Build Graph
        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]) {
                    graph.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
                    graph.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
                }
            }
        }

        boolean[] visited = new boolean[n];
        int numOfComponents = 0;

        // DFS to count number of connected components
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                numOfComponents++;
            }
        }

        return n - numOfComponents;
    }

    private void dfs(
        int node, Map<Integer, List<Integer>> graph, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
        visited[node] = true;

        while (!stack.isEmpty()) {
            int current = stack.pop();

			for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
				if (!visited[neighbor]) {
					visited[neighbor] = true;
					stack.push(neighbor);
				}
			}
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def removeStones(stones):
    from collections import defaultdict

    def dfs(x, visited, graph):
        stack = [x]
        while stack:
            node = stack.pop()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)

    graph = defaultdict(list)
    for i, (x1, y1) in enumerate(stones):
        for j, (x2, y2) in enumerate(stones):
            if i != j:
                if x1 == x2 or y1 == y2:
                    graph[i].append(j)

    visited = set()
    num_of_components = 0
    for i in range(len(stones)):
        if i not in visited:
            visited.add(i)
            dfs(i, visited, graph)
            num_of_components += 1

    return len(stones) - num_of_components

Complexity

  • Time: O(n^2)
  • Space: O(n)

Method 3 - Using union find

We can also union find data structure to find number of components.

Here are the steps:

  1. Union-Find Data Structure: Implement find and union methods to manage connected components.
  2. Map Rows and Columns to Unique Indices: Treat each stone as belonging to a unique node in the union-find structure.
  3. Union Rows and Columns: For each stone, perform a union operation for the row and column indices.
  4. Counting Components: Use the union-find structure to determine the number of unique components.
  5. Calculate the Answer: The maximum number of stones that can be removed is the total number of stones minus the number of unique components.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

public class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UnionFind uf = new UnionFind(20000);

        // Join nodes for stones in the same row or column
        for (int[] stone : stones) {
            uf.union(stone[0], stone[1] + 10001); // separate row and column
                                                  // indices to avoid collision
        }

        // Count unique components
        Set<Integer> uniqueComponents = new HashSet<>();
        for (int[] stone : stones) {
            uniqueComponents.add(uf.find(stone[0]));
        }

        // Maximum stones that can be removed
        return n - uniqueComponents.size();
    }

    static class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // path compression
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX != rootY) {
                // union by rank
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }
}

Complexity

  • ⏰ Time complexity: O(α(n)) where α(n) is the inverse Ackermann function, extremely slow-growing, effectively close to constant time.
    • Find operations: α(n) per operation due to path compression.
  • 🧺 Space complexity: O(1)