# 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

关键思路在于转化问题为Number of Islands：

每次移除的stone必须是一个属于connected component（也就是一个island）中的坐标，那么最后剩余的，就将是每个island都最后一个点。因此总的可以移除的stone数目：`number os stones to be removed = total number of stones - number of islands`

### Union Find 并查集

#### HashMap implementation of Union Find

966 ms, faster than 0.98%

```java
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

```java
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)
            seen.add(dsu.find(stone[0]));

        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

```java
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) {
        visited.add(idx);

        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

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/union_find/most-stones-removed-with-same-row-or-column.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.