Java simple Union-Find solution beating 97.94%


  • 3
    public class Solution {
        private int[] roots;
        private int count;
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            int[][] matrix = new int[m][n];
            roots = new int[m*n];
            List<Integer> res = new ArrayList<>();
            // initialize roots
            for(int i=0; i<m*n; i++){
                roots[i] = i;
            }
            for(int[] pos:positions){
                int x = pos[0], y = pos[1];
                // check if current position is already land
                if(1==matrix[x][y]){
                    res.add(count);
                    continue;
                }
                int cur = x*n+y;
                matrix[x][y] = 1;
                ++count;
                // visit neighbors
                if(y>0 && matrix[x][y-1]>0){
                    union(cur, cur-1);
                }
                if(y<n-1 && matrix[x][y+1]>0){
                    union(cur, cur+1);
                }
                if(x>0 && matrix[x-1][y]>0){
                    union(cur, cur-n);
                }
                if(x<m-1 && matrix[x+1][y]>0){
                    union(cur, cur+n);
                }
                res.add(count);
            }
            return res;
        }
        private int find(int t){
            while(t!=roots[t]){
                roots[t] = roots[roots[t]];
                t = roots[t];
            }
            return t;
        }
        private void union(int a, int b){
            int aroot = find(a), broot = find(b);
            if(aroot!=broot){
                roots[aroot] = broot;
                --count;
            }
        }
    }

  • 0
    F

    I find there is a bug in the program.
    If dictionary= {{0,0}, {0,1}, {1,2}, {2,1},{2,1}}
    The out put is : [1, 1, 2, 3, 4]
    But the out put should be [1, 1, 2, 3, 3]


  • 0

    @fei38 Thank you for pointing out that a position in the array may already be a land. I have updated my code to avoid such bug. And I found that even OJ did not take this case into consideration.


  • 0
    F

    @sky-xu Thank you for modifying your code and reply so fast. And thank you for share your code. I learnt a lot.


  • 0
    F

    @sky-xu Can I replace the following code:
    '''
    if(1==matrix[x][y]){
    res.add(res.get(res.size()-1));
    continue;
    }
    '''
    with:
    '''
    if(1==matrix[x][y]){
    res.add(count);
    continue;
    }
    '''
    I think that would be more easy. Thank you!


  • 0

    @fei38 Yes you are right! I didn't notice that. Thanks for pointing out! Really appreciate that.


  • 0

    @fei38 said in Java simple Union-Find solution beating 97.94%:

    {{0,0}, {0,1}, {1,2}, {2,1},{2,1}}

    It is good to remove a potential bug. But I do not think remove duplicate is the main point of this problem. That is why OJ does not take it into account.


Log in to reply
 

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