Java TreeMap O(1) add and O(n) get Solution with Explanation

• The basic idea is to use two map to store intervals. One map stores the start of each interval and its length; the other map stores the end of each interval and its length. When a new value is added, check whether (val+1) or (val -1) is the start or end of one interval, if so, merge and update both maps.

``````public class SummaryRanges {

TreeMap<Integer, Integer> fromLeft;
TreeMap<Integer, Integer> fromRight;

/** Initialize your data structure here. */
public SummaryRanges() {
fromLeft = new TreeMap<>();
fromRight = new TreeMap<>();
}

public void addNum(int val) {
if (fromRight.containsKey(val) || fromLeft.containsKey(val)) {
return;
}

int leftLen = fromLeft.getOrDefault(val + 1, 0) + 1;
int rightLen = fromRight.getOrDefault(val - 1, 0) + 1;

fromLeft.put(val, leftLen + rightLen - 1);
fromRight.put(val + leftLen - 1, leftLen + rightLen - 1);

fromRight.put(val, leftLen + rightLen - 1);
fromLeft.put(val - rightLen + 1, leftLen + rightLen - 1);
}

public List<Interval> getIntervals() {

List<Interval> ans = new ArrayList<>();
int limit = Integer.MIN_VALUE;
for (int key : fromLeft.keySet()) {
if (key > limit) {
limit = key + fromLeft.get(key) - 1;
}
}

return ans;
}
``````

}

• What makes you think those TreeMap operations are O(1)?

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