Simple UnionFind Java solution. Beat 75%


  • 3

    There are many short excellent solutions for this particular problem. However, this problem can also be solved by union find. There is a very good material to learn union find.

    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    public class Solution {
        int[] id;
        int[] sz;
        Map<Integer, Integer> map;
        
        public int longestConsecutive(int[] nums) {
            id = new int[nums.length];
            sz = new int[nums.length];
            map = new HashMap<>();
            
            for (int i = 0; i < nums.length; i++) {
                insert(nums[i], i);
            }
            
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                res = Math.max(res, sz[i]);
            }
            
            return res;
        }
        
        private void insert(int num, int index) {
            if (!map.containsKey(num)) {
                map.put(num, index);
                id[index] = index;
                sz[index] = 1;
                if (map.containsKey(num - 1)) {
                    unite(num - 1, num);
                }
                if (map.containsKey(num + 1)) {
                    unite(num + 1, num);
                }
            }
        }
        
        private void unite(int num1, int num2) {
            int p = findSet(map.get(num1));
            int q = findSet(map.get(num2));
            if (p != q) {
                if (sz[p] > sz[q]) {
                    id[q] = p;
                    sz[p] += sz[q];
                } else {
                    id[p] = q;
                    sz[q] += sz[p];
                }
            }
        }
        
        private int findSet(int p) {
            if (id[p] != p) {
                id[p] = findSet(id[p]);
            }
            return id[p];
        }
    }
    

  • 0
    M

    I understand that there are other solutions but it's very interesting to see other point of views! That was really helpful! Thanks :)


  • 0

    @mehran thanks:)


  • 0

    Nice solution.

    But does it run in linear time complexity?


  • 0

    No it's not linear complexity. If you read the slides I provided, it's (M + N) lg* N, where M union-find ops on a set of N objects


  • 0

    @Rosti Although I think it's hard to prove lol


  • 0

    @shuangling Thanks:)


  • 0
    A

    Can you get rid of the last loop by maintaining a max each time you update the sz array?


  • 0

    @aval I think you can do so, using static variable? But I personally think having an extra loop is better to separate the logics:)


Log in to reply
 

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