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)

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

/*
因為一開始就沒有任何資料, 逐筆加入的, 所以要把加入的 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)

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
*/