Removing Stones From a Shared Yard
Solve this ProblemSome cells of a grid each hold one stone. You may lift a stone off the grid only if another stone is still standing somewhere in the same row or the same column. Work out the greatest number of stones that can be lifted off, one after another.
Stones that share a row or a column form groups, and in every group all stones but one can be removed. Union-find on the rows and columns (instead of on the stones) counts the groups in one pass.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ stones.length ≤ 10; stones[i] = [row, column] with 0 ≤ row, column ≤ 9; all stones are at different positions - ◆
A stone may be lifted off only while some other stone is still on the grid in its row or in its column - ◆
Stones are removed one at a time; the same stone cannot be removed twice - ◆
Return the largest number of stones that can be removed
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Group the Stones by Spreading Labels
BruteStones that share a row or a column belong to the same group, and all stones of a group except one can be removed (remove them in an order that always leaves a partner: for example peel off stones from the outside of a tree of the group). So the answer is (number of stones) − (number of groups). To count the groups, give each stone its own number as label and sweep repeatedly over all pairs: whenever two stones share a row or column, the one with the larger label takes the smaller label. When nothing changes, the stones still carrying their own number are one per group.
O(k³)O(k)1class Solution {
2 public int maxRemovable(int[][] stones) {
3 int n = stones.length;
4 int[] label = new int[n];
5 for (int i = 0; i < n; i++) label[i] = i;
6 boolean changed = true;
7 while (changed) {
8 changed = false;
9 for (int i = 0; i < n; i++) {
10 for (int j = 0; j < n; j++) {
11 boolean touching = stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1];
12 if (touching && label[j] < label[i]) {
13 label[i] = label[j];
14 changed = true;
15 }
16 }
17 }
18 }
19 int groups = 0;
20 for (int i = 0; i < n; i++) {
21 if (label[i] == i) groups++;
22 }
23 return n - groups;
24 }
25}Optimal — Union-Find Over Rows and Columns
OptimalDo not compare stones with each other at all. Make each row and each column a node of a union-find structure (rows 0–9, columns as 10–19). A stone at (r, c) is an edge that joins row r and column c, so all stones of the same row or column end up in one group. The number of groups equals the number of distinct roots among the rows of the stones. The answer is (number of stones) − (number of groups).
O(k · α)O(1) (20 nodes)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public int maxRemovable(int[][] stones) {
11 int[] parent = new int[20];
12 for (int i = 0; i < 20; i++) parent[i] = i;
13 for (int[] stone : stones) {
14 parent[find(parent, stone[0])] = find(parent, 10 + stone[1]);
15 }
16 Set<Integer> groups = new HashSet<>();
17 for (int[] stone : stones) groups.add(find(parent, stone[0]));
18 return stones.length - groups.size();
19 }
20}