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

• ``````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<>();
}

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<>();