# 947. Most Stones Removed with Same Row or Column

might say Lee's explanation is the best for this Q

<https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solutions/197668/count-the-number-of-islands-o-n/>

but he uses \~ , for O(n) processing, digest later

T: O(n^2)??? -> should O(N⋅α(K))

S: O(n)

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

        // 2D to 1D corodinate and map to node id (0~n-1) 
        Map<Integer, Integer> nodeIdMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            nodeIdMap.put(encode(stones[i][0], stones[i][1]), i);
        }

        // row, col has elements, record x -> has many 1D(x,y), y -> has many 1D(x,y)
        Map<Integer, List<Integer>> rowPointMap = new HashMap<>();
        Map<Integer, List<Integer>> colPointMap = new HashMap<>();
        for (int[] stone : stones) {
            int x = stone[0];
            int y = stone[1];
            rowPointMap.putIfAbsent(stone[0], new ArrayList<>());
            rowPointMap.get(stone[0]).add(encode(x, y));

            colPointMap.putIfAbsent(stone[1], new ArrayList<>());
            colPointMap.get(stone[1]).add(encode(x, y));
        }

        // union all stone by row
        for (int rowKey : rowPointMap.keySet()) {
            List<Integer> list = rowPointMap.get(rowKey);
            int firstId = nodeIdMap.get(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                int nextId = nodeIdMap.get(list.get(i));
                uf.union(firstId, nextId);
            }
        }
        // union all stone by col
        for (int colKey : colPointMap.keySet()) {
            List<Integer> list = colPointMap.get(colKey);
            int firstId = nodeIdMap.get(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                int nextId = nodeIdMap.get(list.get(i));
                uf.union(firstId, nextId);
            }
        }
        // total stone number - component number
        return n - uf.getComponentsCount();
    }
    private int encode(int x, int y) {
        return x*10000 + y;
    }
    
    class UnionFind {
        int[] parent;
        int count;
        UnionFind(int n) {
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                this.count--;
                return true;
            }
            return false;
        }
        private int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        private int getComponentsCount() {
            return this.count;
        }
    }
}
/*
[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]


o o x
o x o 
o x o

so key is we can use row and col to make
stone connected

and in one component, at last we'll leave one stone

so how many stone can be eliminated: total stone number - component number
so ex1: 6 - 1 = 5

how to connect by row and col? use union find
but this one is 2D array, so we'll use 2D to 1D skill to note which node mapping to xy
xy -> node id
*/
```
````

其實不需要 1d 對應...

直接對應 0 \~ n-1 node 編號即可..

T: O(N⋅α(K))

S: O(n)

````java
```java
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UnionFind uf = new UnionFind(n);
        Map<Integer, List<Integer>> rowMap = new HashMap<>();
        Map<Integer, List<Integer>> colMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int x = stones[i][0];
            int y = stones[i][1];
            rowMap.putIfAbsent(x, new ArrayList<>());
            rowMap.get(x).add(i);

            colMap.putIfAbsent(y, new ArrayList<>());
            colMap.get(y).add(i);
        }
        for (int key : rowMap.keySet()) {
            List<Integer> nodeIdList = rowMap.get(key);
            int firstNodeId = nodeIdList.get(0);
            for (int i = 1; i < nodeIdList.size(); i++) {
                uf.union(firstNodeId, nodeIdList.get(i));
            }
        }
        for (int key : colMap.keySet()) {
            List<Integer> nodeIdList = colMap.get(key);
            int firstNodeId = nodeIdList.get(0);
            for (int i = 1; i < nodeIdList.size(); i++) {
                uf.union(firstNodeId, nodeIdList.get(i));
            }
        }

        return n - uf.getComponentCount();
    }
    class UnionFind {
        private int[] parent;
        private int count;
        UnionFind(int n) {
            this.parent = new int[n];
            this.count = n;
            for (int i = 0; i < n ; i++) {
                this.parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                count--;
                return true;
            }
            return false;
        }
        public int getComponentCount() {
            return this.count;
        }
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}
```
````


---

# 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://timmybeeflin.gitbook.io/cracking-leetcode/union-find/947.-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.