1D Union Find Java solution, easily generalized to other problems


  • 39
    Y

    For any problem I work on, I will try to generalize some reusable template out for future use. We have limited time during interview and too much to worry about, so having some code template to use is very handy. For this problem, although it is easier and probably suggested to use BFS, but Union find also comes handy and can be easily extended to solve Island 2 and Surrounded regions.

    I separate all the union find logic in a separate class and use 1d version to make the code clear. I also use a 2d array for the 4 direction visit. int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}};

        int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}};
        public int numIslands(char[][] grid) {  
            if (grid == null || grid.length == 0 || grid[0].length == 0)  {
                return 0;  
            }
            UnionFind uf = new UnionFind(grid);  
            int rows = grid.length;  
            int cols = grid[0].length;  
            for (int i = 0; i < rows; i++) {  
                for (int j = 0; j < cols; j++) {  
                    if (grid[i][j] == '1') {  
                        for (int[] d : distance) {
                            int x = i + d[0];
                            int y = j + d[1];
                            if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {  
                                int id1 = i*cols+j;
                                int id2 = x*cols+y;
                                uf.union(id1, id2);  
                            }  
                        }  
                    }  
                }  
            }  
            return uf.count;  
        }
    

    Union Find:

        class UnionFind {
            int[] father;  
            int m, n;
            int count = 0;
            UnionFind(char[][] grid) {  
                m = grid.length;  
                n = grid[0].length;  
                father = new int[m*n];  
                for (int i = 0; i < m; i++) {  
                    for (int j = 0; j < n; j++) {  
                        if (grid[i][j] == '1') {
                            int id = i * n + j;
                            father[id] = id;
                            count++;
                        }
                    }  
                }  
            }
            public void union(int node1, int node2) {  
                int find1 = find(node1);
                int find2 = find(node2);
                if(find1 != find2) {
                    father[find1] = find2;
                    count--;
                }
            }
            public int find (int node) {  
                if (father[node] == node) {  
                    return node;
                }
                father[node] = find(father[node]);  
                return father[node];
            }
        }

  • 0
    B

    Could you please spare some time to help me with this? I have been stuck for the whole afternoon with this. I don't know what is wrong.

    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        createUnion(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') { continue; }
                int id = i * n + j;
                
                if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                    int id1 = (i - 1) * n + j;
                    union(id, id1);
                }
                if (i + 1 < m && grid[i + 1][j] == '1') {
                    int id1 = (i + 1) * n + j;
                    union(id, id1);
                }
                if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                    int id1 = i * n + (j - 1);
                    union(id, id1);
                }
                if (j + 1 < n && grid[i][j + 1] == '1') {
                    int id1 = i * n + (j + 1);
                    union(id, id1);
                }
            }
        }
        
        // Set<Integer> count = new HashSet<Integer>();
        // for (Integer key : father.keySet()) {
        //     count.add(find(key));
        // }
        // return count.size();
        return count;
    }
    
    int count;
    Map<Integer, Integer> father = new HashMap<Integer, Integer>();
    
    public void createUnion(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') { continue; }
                int id = i * n + j;
                father.put(id, id);
                count++;
            }
        }
    }
    
    public void union(int a, int b) {
        int fa = find(a), fb = find(b);
        if (fa != fb) {
            father.put(a, fb);
            count--;
        }
    }
    
    public int find(int a) {
        if (a != father.get(a)) {
            father.put(a, find(father.get(a)));
        }
        return father.get(a);
    }
    

    Thank you in advance!! Any help will be greatly appreciated!!


  • 1
    B

    Solved.

    union(a, b) should update the father_a rather than a itself.


  • 2

    How can I mark/favorite your answer like on StackOverflow?
    :)
    Thumbs up on your clarity!


  • 0
    J

    said in 1D Union Find Java solution, easily generalized to other problems:

    father = new int[m*n];

    I would suggest initialize father, Arrays.fill(father, -1). otherwise, father[0] = [0] by default. It might cause problem in future.


  • 0

    @jeffrey.wang.58555 cuz what problem?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.