# Java solution using TreeMap, real O(logN) per adding.

• Use TreeMap to easily find the lower and higher keys, the key is the start of the interval.
Merge the lower and higher intervals when necessary. The time complexity for adding is O(logN) since lowerKey(), higherKey(), put() and remove() are all O(logN). It would be O(N) if you use an ArrayList and remove an interval from it.

``````public class SummaryRanges {
TreeMap<Integer, Interval> tree;

public SummaryRanges() {
tree = new TreeMap<>();
}

if(tree.containsKey(val)) return;
Integer l = tree.lowerKey(val);
Integer h = tree.higherKey(val);
if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
tree.get(l).end = tree.get(h).end;
tree.remove(h);
} else if(l != null && tree.get(l).end + 1 >= val) {
tree.get(l).end = Math.max(tree.get(l).end, val);
} else if(h != null && h == val + 1) {
tree.put(val, new Interval(val, tree.get(h).end));
tree.remove(h);
} else {
tree.put(val, new Interval(val, val));
}
}

public List<Interval> getIntervals() {
return new ArrayList<>(tree.values());
}
}``````

• Nice to learn the TreeMap, did not have a good chance to use it yet :)

• Question: What if the val of addNum is already in the tree as start value?
lowerKey and higherKey find those with 'strictly' lower or higher values, so I think it will end up with creating a new interval when it is supposed to be absorbed.

• It returns directly if the val is already in the tree. The first line of addNum method: if(tree.containsKey(val)) return;

• gotcha, thank you.

• This post is deleted!

• But there is a "tree.remove(h)", what if the val has been removed, and it will end up creating a new {val, val} interval, because the tree does not contain the key any more.

• very brilliant solution! really really smart!

• In the second else if condition:

else if(l != null && tree.get(l).end + 1 >= val) {
tree.get(l).end = Math.max(tree.get(l).end, val);

why do we need, tree.get(l).end + 1 >= val
we could have just said if it is equal or not, tree.get(l).end + 1 can't be greater than val, because in that case it means that the given number(val) already exists in the interval and the code will return from the first line of this function.

Please explain if there is something I missed.

• val can be fit in the Interval, which means there may have duplicates.

• This post is deleted!

• ``````//HI thanks for you idea, and code. for ours c++, we don't have  TreeMap, but We can       use map, it's a ordered map. but map doesn't  have lowerKey, so I implement one .The code is below:c++
private:
map<int, Interval> orderedmap;
int lowerKey(map<int, Interval> &orderedmap, int key){
auto pos = orderedmap.lower_bound(key);
if(pos == orderedmap.begin()) {
return -1;
}
return (--pos)->first;
}
int higherKey(map<int, Interval> &orderedmap, int key){
auto pos = orderedmap.upper_bound(key);
if(pos == orderedmap.end() ){
return -1;
}
return pos->first;
}
public:
/** Initialize your data structure here. */
SummaryRanges() {

}
if(orderedmap.find(val) != orderedmap.end()){
return ;
}
int l = lowerKey(orderedmap,val);
int r = higherKey(orderedmap,val);
if(l != -1 && r != -1 && orderedmap[l].end+1 == val && r == val+1){
orderedmap[l].end = orderedmap[r].end;
orderedmap.erase(r);
}else if(l != -1 && orderedmap[l].end+1 >= val){
orderedmap[l].end = max(orderedmap[l].end ,val);
}else if(r != -1 && r == val+1){
orderedmap[val] = Interval (val,orderedmap[r].end);
orderedmap.erase(r);
}else{
Interval iv(val,val);
orderedmap[val] = Interval (val,val);
}
}

vector<Interval> getIntervals() {
vector<Interval> res;
for(auto &i : orderedmap){
res.push_back(i.second);
}
return res;
}
``````

};

• @qianzhige
getIntervals is O(n) ! For h, you can just use get(val + 1)

• @aman13 First,you need to know, the tree only contains the lowest key of one interval. Then for example, 1,2,3,2…… the tree will contain:
1: 1 [1,1]
2: 1 [1,2]
3: 1 [1,3]
4: here, you might encounter the case that tree.get(1).end=3 which larger than newly inputted two

• @qianzhige
very brilliant idea, but why not use TreeSet?
Here is my AC TreeSet version, also a little slower...

``````public class SummaryRanges {
TreeSet<Interval> set;

/** Initialize your data structure here. */
public SummaryRanges() {
set = new TreeSet(new Comparator<Interval>() {
@Override
public int compare(Interval a, Interval b) {
return a.start == b.start? a.end - b.end: a.start - b.start;
}
});
}

Interval interval = new Interval(val, val);
if (set.contains(interval)) return ;
Interval low = set.lower(interval), high = set.higher(interval);
// check if this val is a start of some interval
if (high != null && high.start == val) return ;
// merge three intervals
if (low != null && low.end + 1 == val &&
high != null && val + 1 == high.start) {
low.end = high.end;
set.remove(high);
}
// merge lower and this interval
else if (low != null && low.end + 1 >= val) {
low.end = Math.max(low.end, val);
}
// merge this and higher interval
else if (high != null && val + 1 == high.start) {
high.start = val;
}
// insert this interval
else {
}
}

public List<Interval> getIntervals() {
return new ArrayList<>(tree.values());
}
}``````

• I think using `floorKey` instead of `lowerKey` is better.
Here is my code:

``````public class SummaryRanges {

TreeMap<Integer, Interval> treeMap;

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

Integer floor=treeMap.floorKey(val);
if (floor==null || treeMap.get(floor).end<val-1) {
Interval interval=treeMap.remove(val+1);
treeMap.put(val, new Interval(val, interval==null?val:interval.end));
}
else {
Interval interval=treeMap.get(floor);
if (interval.end>=val) return;
Interval next=treeMap.remove(val+1);
interval.end=next==null?val:next.end;
treeMap.put(floor, interval);
}
}

public List<Interval> getIntervals() {
return new ArrayList<>(treeMap.values());
}
}
``````

• @iaming
Yes, get is `O(n)`, but the intention here was to optimize the add to `O(log(n))`, since the get queries might be relatively small compared to the streaming add calls. A minior optimization that can be done on get is to create a new list only if the treeMap was updated since last getCall.

If you want the get to be optimized to `O(1)`, you can create the list during add call, which again makes it `O(n)`.

• Thanks for sharing! I'm wondering could we solve it like what we did for 128 Longest Consecutive Sequence.
We don't try to find closest lower or higher entry, conversely only find val+/-1 and union consecutive range.
In this way, the time complexity of add() would be O(1) and getIntervals() would be O(NlogN), am I correct?

ps: I assume the N in O(NlogN) should be very small since I only keep two ends of interval.

``````    // Key - left or right boundary value of range, Value - size of range
private Map<Integer, Integer> ranges = new HashMap<>();

// Since middle val is removed, an extra set is required to de-duplicate
private Set<Integer> dup = new HashSet<>();

int left = ranges.containsKey(val - 1) ? ranges.remove(val - 1) : 0;
int right = ranges.containsKey(val + 1) ? ranges.remove(val + 1) : 0;
int sum = left + right + 1;

if (left > 0) ranges.put(val - left, sum);
if (right > 0) ranges.put(val + right, sum);
if (left == 0 || right == 0) ranges.put(val, sum); // remove middle val to speed up getInt()
}

public List<Interval> getIntervals() {
List<Interval> ret = new ArrayList<>();
List<Integer> keys = new ArrayList<>(ranges.keySet());
Collections.sort(keys);

int last = Integer.MIN_VALUE;
for (int left : keys) {
int size = ranges.get(left);
if (last < left) {
ret.add(new Interval(left, left + size - 1));
last = left + size - 1;
}
}
return ret;
}
``````

• @hyj143 `tree.lowerKey` will find the possible interval anyway

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