Share my 1-D (m*n) solution beating 97.85%


  • 0

    The idea is the same, using UnionFind, while it might be faster if we use 1-d array.

    public class Solution {
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            int[] parent = new int[m*n];
            int count=0;
            Arrays.fill(parent, -1);
            List<Integer> ret = new ArrayList<Integer>();
            for(int[] d:positions){
                int cur = d[0]*n+d[1];
                count++;
                parent[cur] = cur;
                if(cur%n!=0 && parent[cur-1]!=-1){
                    int p1 = find(parent, cur), p2 = find(parent, cur-1);
                    if(p1!=p2){ count--; parent[p1] = p2;}
                }
                if((cur+1)%n!=0 && parent[cur+1]!=-1){
                    int p1 = find(parent, cur), p2 = find(parent, cur+1);
                    if(p1!=p2){ count--; parent[p1] = p2;}
                }
                if(cur-n>=0 && parent[cur-n]!=-1){
                    int p1 = find(parent, cur), p2 = find(parent, cur-n);
                    if(p1!=p2){ count--; parent[p1] = p2;}
                }
                if(cur+n<m*n && parent[cur+n]!=-1){
                    int p1 = find(parent, cur), p2 = find(parent, cur+n);
                    if(p1!=p2){ count--; parent[p1] = p2;}
                }
                ret.add(count);
            }
            return ret;
        }
        public int find(int[] parent, int p){
            while(p!=parent[p]){
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }
    }
    

Log in to reply
 

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