My Straightforward Java Union-Find Solution With Explanation and Thoughts


  • 0
    Y

    The reason to use union-find is that it stores all known islands, so we don't need to search the entire matrix every time a piece of land is added.

    I used a 1-d array in my union-find data structure. When use it to store a 2-d array index pair, simply convert the pair into its numbering in a 1-d array.

    Initially we set the union-find array to -1 to mark the entire matrix as water. Keep a counter result to count the lands we have. When we add a land, we set the UF array id[index] = index, because initially everything is with itself. We also increment the counter result by 1. After that, we need to check whether the newly added land connects previously added lands. We check the up, down, left, and right positions of the newly added land. If there is a position that is also a land, we want to union these two lands and decrement result by 1, because the newly added land is connected with its neighbor and we must not double count the connected land. Overall, result = result + 1 - #islandsConnectedwithIndex. Since we only search for 4 directions, it's easy to prove by enumerate all possible conditions.

    My code isn't the best, but it uses a quite standard UF data structure and hopefully it's easy to understand.

    public class Solution {
        private class QuickUF {
            private int[] id; // id[i] is parent of i
    	
            public QuickUF(int N) {
                id = new int[N];
                Arrays.fill(id, -1);    // at first, there is no land
            }
    	
            private int find(int i) {
                while (i != id[i]) {    // trace to root
                    id[i] = id[id[i]];  // path compression (halving)
                    i = id[i];
                }
                return i;
            }
        	
            public boolean connected(int p, int q) {
                return find(p) == find(q);
            }
        	
        	public void union(int p, int q) {
        	    int i = find(p), j = find(q);
        	    id[i] = j;
            }
            
            public void setLand(int i) {
                id[i] = i;
            }
            
            public boolean isLand(int i) {
                return id[i] != -1;
            }
        }
        
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            QuickUF UF = new QuickUF(m*n);
            List<Integer> L = new ArrayList<>();
            int result = 0;
            for (int i = 0; i < positions.length; i++) {
                int[] pos = positions[i];
                int index = getIndex(pos[0], pos[1], n);
                UF.setLand(index);
                result++;
                if (isValid(pos[0], pos[1]-1, m, n, UF) && !UF.connected(index, getIndex(pos[0], pos[1]-1, n))) {
                    UF.union(index, getIndex(pos[0], pos[1]-1, n));
                    result--;
                }
                if (isValid(pos[0], pos[1]+1, m, n, UF) && !UF.connected(index, getIndex(pos[0], pos[1]+1, n))) {
                    UF.union(index, getIndex(pos[0], pos[1]+1, n));
                    result--;
                }
                if (isValid(pos[0]-1, pos[1], m, n, UF) && !UF.connected(index, getIndex(pos[0]-1, pos[1], n))) {
                    UF.union(index, getIndex(pos[0]-1, pos[1], n));
                    result--;
                }
                if (isValid(pos[0]+1, pos[1], m, n, UF) && !UF.connected(index, getIndex(pos[0]+1, pos[1], n))) {
                    UF.union(index, getIndex(pos[0]+1, pos[1], n));
                    result--;
                }
                L.add(result);
            }
            return L;
        }
        
        // returns the position (x,y)'s index in an 1-d array
        private int getIndex(int x, int y, int n) {
            return x*n + y;
        }
        
        // check if a position is valid for land union
        private boolean isValid(int x, int y, int m, int n, QuickUF UF) {
            return x >= 0 && x < m && y >= 0 && y < n && UF.isLand(getIndex(x, y, n));
        }
        
        
    }
    

    Final remarks:
    I actually came up with a not-so-good solution before, where I would store all available lands connected to the current index first, then I loop through their combination to check and decrement result. It was a bad idea that made my code complex and hard to debug, because there were several cases and I needed to handle them in the correct order, otherwise the result wasn't decremented correctly. I realized the importance of thinking about the best solution before coding now.


Log in to reply
 

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