Java solution with time complexity O(k log mn)


  • 0
    S

    Most of the solutions initialize an array with size m * n. The initialization would take O(mn) times. Use a map instead of the array can help us bypass the initialization.

    class Solution {
        class UnionSet {
            public int size = 0;
            private Map<Integer, Integer> par = new HashMap<>();
            public void add(int a) {
                if (!par.containsKey(a)) {
                    par.put(a, a);
                    size++;
                }
            }
            public void union(int a, int b) {
                int pa = find(a);
                int pb = find(b);
                if (pa == -1 || pb == -1 || pa == pb) return;
                par.put(pa, pb);
                size--;
            }
            private int find(int x) {
                Integer parent = par.get(x);
                if (parent == null) return -1;
                if (parent == x) {
                    return x;
                }
                par.put(x, find(parent));
                return par.get(x);
            }
        }
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            int[] dir = {0, 1, 0, -1, 0};
            UnionSet unionSet = new UnionSet();
            List<Integer> ans = new ArrayList<>();
            for (int[] pos : positions) {
                unionSet.add(pos[0] * n + pos[1]);
                for (int i = 0; i < 4; i++) {
                    int x = pos[0] + dir[i];
                    int y = pos[1] + dir[i + 1];
                    if (x < 0 || x >= m || y < 0 || y >= n) {
                        continue;
                    }
                    unionSet.union(pos[0] * n + pos[1], x * n + y);
                }
                ans.add(unionSet.size);
            }
            return ans;
        }
    }
    
    

Log in to reply
 

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