Java disjoint set solution, amortized O(1) per addNum


  • 0
    J
    class SummaryRanges {
        class Node {
            int rank;
            Interval intv;
            Node p;
            Node(Interval i) {
                rank = 0;
                intv = i;
                p = this;
            }
        }
        
        private Node parent(Node root) {
            if (root.p != root) {
                root.p = parent(root.p);
            }
            return root.p;
        }
        
        private Node union(Node left, Node right) {
            Node l = parent(left);
            Node r = parent(right);
            Interval intv = new Interval(l.intv.start, r.intv.end);
            if (l.rank >= r.rank) {
                r.p = l;
                r.intv = null;
                l.intv = intv;
                if (l.rank == r.rank) l.rank++;
                return l;
            } else {
                l.p = r;
                l.intv = null;
                r.intv = intv;
                return r;
            }
        }
        
        private Map<Integer, Node> map;
        /** Initialize your data structure here. */
        public SummaryRanges() {
            map = new HashMap<>();
        }
        
        public void addNum(int val) {
            if (map.containsKey(val)) return;
            Node left = map.get(val - 1);
            Node right = map.get(val + 1);
            if (left != null) {
                Interval intv = parent(left).intv;
                if (val > intv.end) intv.end = val;
                map.put(val, left);
            }
            if (right != null) {
                Interval intv = parent(right).intv;
                if (val < intv.start) intv.start = val;
                if (left != null && parent(left).intv.end == intv.start) {
                    Node newP = union(left, right);
                    map.put(val, newP);
                } else map.put(val, right);
            } else if (left == null) {
                Interval intv = new Interval(val, val);
                Node cur = new Node(intv);
                map.put(val, cur);
            }
        }
        
        public List<Interval> getIntervals() {
            Set<Interval> res = new HashSet<>();
            for (int key: map.keySet()) res.add(parent(map.get(key)).intv);
            List<Interval> ret = new ArrayList<>(res);
            Collections.sort(ret, (Interval a, Interval b) -> a.start - b.start);
            return ret;
        }
    }
    

Log in to reply
 

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