# Most Stones Removed with Same Row or Column

Medium

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

Now, a_move_consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

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

Example 2:

``````Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3``````

Example 3:

``````Input: stones = [[0,0]]
Output: 0``````

Note:

1. `1 <= stones.length <= 1000`

2. `0 <= stones[i][j] < 10000`

## Analysis & Solution

### Union Find 并查集

#### HashMap implementation of Union Find

966 ms, faster than 0.98%

``````class Solution {
public static int numberOfIslands;
public static HashMap<String, String> parent;

private String buildKey(int[] coordinate) {
return coordinate[0] + "," + coordinate[1];
}

public int removeStones(int[][] stones) {
numberOfIslands = stones.length;
parent = new HashMap<>();
for (int[] stone: stones) {
String s = buildKey(stone);
parent.put(s, s);
}

for (int[] s1: stones) {
String key1 = buildKey(s1);
for (int[] s2: stones) {
String key2 = buildKey(s2);
if (s1[0] == s2[0] || s1[1] == s2[1]) {
union(key1, key2);
}
}
}
return stones.length - numberOfIslands;
}

private String find(String key) {
if (!parent.get(key).equals(key)) {
parent.put(key, find(parent.get(key)));
}
return parent.get(key);
}
private void union(String k1, String k2) {
String p1 = find(k1);
String p2 = find(k2);
if (!p1.equals(p2)) {
parent.put(p1, p2);
numberOfIslands--;
}
}
}``````

#### Array Implementation of Union Find

``````class Solution {
public int removeStones(int[][] stones) {
int N = stones.length;
DSU dsu = new DSU(20000);

for (int[] stone: stones)
dsu.union(stone[0], stone[1] + 10000);

Set<Integer> seen = new HashSet();
for (int[] stone: stones)

return N - seen.size();
}
}

class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}``````
• Time Complexity: O(NlogN), where N is the length of `stones`. (If we used union-by-rank, this can be O(N∗α(N)), where α is the Inverse-Ackermann function.)

• Space Complexity: O(N).

### DFS

Recursive Implementation

``````class Solution {
public int removeStones(int[][] stones) {
int islands = 0;

Set<Integer> visited = new HashSet<>();

for (int i = 0; i < stones.length; i++) {
if (visited.contains(i)) continue;
islands++;
dfs(i, stones, visited);
}

return stones.length - islands;
}

private void dfs(int idx, int[][] stones, Set<Integer> visited) {

for (int nextIdx = 0; nextIdx < stones.length; nextIdx++) {
if (visited.contains(nextIdx)) continue;
if (stones[idx][0] == stones[nextIdx][0] ||
stones[idx][1] == stones[nextIdx][1]) {
dfs(nextIdx, stones, visited);
}
}
}
}``````

Stack Implementation

``````class Solution {
public int removeStones(int[][] stones) {
int N = stones.length;

// graph[i][0] = the length of the 'list' graph[i][1:]
int[][] graph = new int[N][N];
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[i][++graph[i][0]] = j;
graph[j][++graph[j][0]] = i;
}

int ans = 0;
boolean[] seen = new boolean[N];
for (int i = 0; i < N; ++i) if (!seen[i]) {
Stack<Integer> stack = new Stack();
stack.push(i);
seen[i] = true;
ans--;
while (!stack.isEmpty()) {
int node = stack.pop();
ans++;
for (int k = 1; k <= graph[node][0]; ++k) {
int nei = graph[node][k];
if (!seen[nei]) {
stack.push(nei);
seen[nei] = true;
}
}
}
}

return ans;
}
}``````

Last updated