# 305. Number of Islands II (union-find)

## naive

BFS in leetcode 200, each cell call BFS one time

T: O(mn\*mn)

S: O(mn)

## union find

T: O(mn)

S: O(mn)

```java
class Solution {
    private int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}};
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        if (positions == null || positions.length == 0) {
            return res;
        }
        UnionFind uf = new UnionFind();
        boolean[][] isLand = new boolean[m][n];
        
        for (int[] position : positions) {
            int x = position[0];
            int y = position[1];
            if (isLand[x][y]) {
                res.add(uf.getNumOfSet());
                continue;
            }
            
            isLand[x][y] = true;
            uf.add(toId(x, y, n));
            
            for (int[] dir : dirs) {
                int neighborX = x + dir[0];
                int neighborY = y + dir[1];
                if (!isValid(neighborX, neighborY, m, n, isLand)) {
                    continue;
                }
                uf.union(toId(x, y, n), toId(neighborX, neighborY, n));
            }
            res.add(uf.getNumOfSet());
        }
        return res;
    }
    /*
      m = 4, n = 9 (4 row, 9 col)
      0  1  2  3 4 5 6 7 8  
      9 10 11 12 => (1,2) => 1*9 + 2 = 11, x*n + y 
    */
    private int toId(int x, int y, int n) {
        return x*n + y;
    }
    private boolean isValid(int x, int y, int m, int n, boolean[][] isLand) {
        return x >= 0 && x < m && y >= 0 && y < n && isLand[x][y];
    }
}

class UnionFind {
    private Map<Integer, Integer> parent;
    private Map<Integer, Integer> sizeOfSet;
    private int numOfSet = 0;
    UnionFind() {
        this.parent = new HashMap<>();
        this.sizeOfSet = new HashMap<>();
    }
    public void add(int x) {
        if (parent.containsKey(x)) {
            return;
        }
        parent.put(x, null);
        sizeOfSet.put(x, 1);
        numOfSet++;
    }
    public int find(int x) {
        int root = x;
        while (parent.get(root) != null) {
            root = parent.get(root);
        }
        
        while (x != root) {
            int xParent = parent.get(x);
            parent.put(x, root);
            x = xParent;
        }
        return root;
    }
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent.put(rootX, rootY);
            numOfSet--;
            sizeOfSet.put(rootY, sizeOfSet.get(rootX)+sizeOfSet.get(rootY));
        }
    }
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
    public int getNumOfSet() {
        return numOfSet;
    }
    public int getSizeOfSet(int x) {
        if (!sizeOfSet.containsKey(x)) {
            return 0;
        }
        return sizeOfSet.get(find(x));
    }
}
```

## new version

```java
/*
因為一開始就沒有任何資料, 逐筆加入的, 所以要把加入的 land 記錄下來
*/
class Solution {
    int dirs[][] = {{0,1},{1,0},{0,-1},{-1,0}};
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        if (positions == null && positions.length == 0) {
            return res;
        }
        boolean[][] isLand = new boolean[m][n];
        UnionFind uf = new UnionFind();
        
        for (int[] position : positions) {
            int x = position[0];
            int y = position[1];
            
            //if (!isLand[x][y]) { // if repeat add same land
            
            isLand[x][y] = true;
            uf.add(convertToId(x, y, n));

            for (int dir[] : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (!isValid(m, n, newX, newY, isLand)) { // still needs check new x, y is also isLand
                    continue;
                }
                uf.union(convertToId(x, y, n),
                        convertToId(newX, newY, n));
                }
            //}
            
            res.add(uf.getNumOfSet()); // if repeat add same land
        }
        return res;
    }
    private boolean isValid(int m, int n, int x, int y, boolean[][] isLand) {
        return x >= 0 && x < m && y >=0 && y < n && isLand[x][y];
    }
    private int convertToId(int x, int y, int n) {
        return x*n + y;
    }
}

class UnionFind {
    private HashMap<Integer, Integer> parent;
    private HashMap<Integer, Integer> sizeOfSet;
    private int numOfSet = 0;;
    UnionFind() {
        parent = new HashMap<>();
        sizeOfSet = new HashMap<>();
    }
    public void add(int x) {
        if (parent.containsKey(x)) {
            return;
        }
        parent.put(x, null);
        sizeOfSet.put(x, 1);
        numOfSet++;
    }
    
    public int find(int x) {
        int root = x;
        while (parent.get(root) != null) {
            root = parent.get(root);
        }
        
        while (root != x) {
            int xParent = parent.get(x);
            parent.put(x, root);
            x = xParent;
        }
        return root;
    }
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            parent.put(rootX, rootY);
            numOfSet--;
            sizeOfSet.put(rootX, sizeOfSet.get(rootX)+sizeOfSet.get(rootY));
        }
    }
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
    public int getSizeOfSet(int x) {
        return sizeOfSet.get(find(x));
    }
    public int getNumOfSet() {
        return numOfSet;
    }
}
```

## final version - simpler union find

T: O(mn)

S: O(mn)

```java
class Solution {
    class UnionFind {
        int count;
        int[] parent;
        UnionFind(int n) {
            count = 0;
            parent = new int[n];
            Arrays.fill(parent, -1);
        }
        
        public boolean isValid(int i) {
            return parent[i] >= 0;
        }
        public void setParent(int i) {
            if (parent[i] == i) {
                return;
            }
            parent[i] = i;
            count++;
        }
        public void union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                count--;
            }
        }
        public int find(int i) {
            if (parent[i] != i) {
                parent[i] = find(parent[i]);
            }
            return parent[i];
        }
        public int getCount() {
            return this.count;
        }
    }
    private static final int[][] DIRS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        UnionFind uf = new UnionFind(m*n); // notice this, give a whole space
        
        for (int[] position : positions) {
            int x = position[0];
            int y = position[1];
            
            // and use id to transform x, y
            int id = convertToId(x, y, n);
            uf.setParent(id);
            
            for (int[] dir : DIRS) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                int newId = convertToId(newX, newY, n);
                if (!isValidRange(newX, newY, m, n) || !uf.isValid(newId)) {
                    continue;
                }
                // union with id
                uf.union(id, newId);
            }
            res.add(uf.getCount());
        }
        return res;
    }
    private int convertToId(int x, int y, int n) {
        return x*n + y; // row*col_size + col
    }
    private boolean isValidRange(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
}

/*
[[0,0],[0,1],[1,2],[1,2]]

1 1
    1
*/
```


---

# 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/dfs-and-bfs/bfs/305.-number-of-islands-ii-union-find.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.