Java disjoint set solution


  • 0
    J
    public class Solution {
        private int parent(int n, HashMap<Integer, Integer> p) {
            int res = p.get(n);
            if (res != n) {
                res = parent(res, p);
                p.put(n, res);
            }
            return res;
        }
        private void link(int left, int right, HashMap<Integer, Integer> p, HashMap<Integer, Integer> len) {
            if (!len.containsKey(left) || !len.containsKey(right)) return;
            int pL = parent(left, p);
            int pR = parent(right, p);
            if (pL == pR) return;
            int lenL = len.get(pL);
            int lenR = len.get(pR);
            if (lenL < lenR) {
                p.put(pL, pR);
                len.put(pR, lenL + lenR);
            } else {
                p.put(pR, pL);
                len.put(pL, lenL + lenR);
            }
        }
    
        public int longestConsecutive(int[] nums) {
            int res = 0;
            HashMap<Integer, Integer> len = new HashMap<>();
            HashMap<Integer, Integer> p = new HashMap<>();
            for (int n: nums) {
                if (len.containsKey(n)) continue;
                len.put(n, 1);
                p.put(n, n);
            }
            for (int n: len.keySet()) {
                link(n, n - 1, p, len);
                link(n + 1, n, p, len);
            }
            for (int n: len.values()) {
                if (n > res) res = n;
            }
            return res;
        }
    }
    

Log in to reply
 

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