# C++ solution using vector and binary search with explanation

• For a new number n, find and return the index of interval [s, t] such that s is the largest 'start' that is smaller than n. If no such interval exists, return -1. This is done using binary search.

For example,

• new number 5, intervals [[1,1], [4,6], [8,8]], binary search returns 1.

• new number 0, intervals [[1,1], [4,6], [8,8]], binary search returns -1.

After we find this 'index', there are three circumstances:

1. intervals[index] already contains val. Do nothing.

2. val can be merged into intervals[index+1]. Modify intervals[index+1].start to val.

3. val can be merged into intervals[index]. Modify intervals[index].end to val.

4. val can't be merged into either interval. Insert Interval( val, val).

Finally, after inserting val, we need to check whether intervals[index] and intervals[index+1] can be merged.

``````class SummaryRanges {
private:
vector<Interval> intervals = vector<Interval>();

int binarySearch(vector<Interval> intervals, int val) {
return binarySearchHelper(intervals, 0, intervals.size(), val);
}

int binarySearchHelper(vector<Interval> intervals, int start, int end, int val) {
if (start == end) return -1;
if (start+1 == end && intervals[start].start < val) return start;

int mid = (start + end)/2;
if (intervals[mid].start == val) {
return mid;
} else if (intervals[mid].start < val) {
return binarySearchHelper(intervals, mid, end, val);
} else { //intervals[mid] > val
return binarySearchHelper(intervals, start, mid, val);
}
}

public:
/** Initialize your data structure here. */
SummaryRanges() {

}

/** For a new number n, find the last(biggest) interval
*  [s,t], such that s < n. If no such interval exists,
*  return -1.
*/
int index = binarySearch(intervals, val);

// intervals[index] contains val
if (index != -1 && intervals[index].end >= val) {
return;
}

if (index != intervals.size()-1 && val + 1 == intervals[index+1].start) {
intervals[index+1].start = val;
} else if (index != -1 && val - 1 == intervals[index].end) {
intervals[index].end = val;
} else {
intervals.insert(intervals.begin() + index + 1, Interval(val, val));
}

//merge intervals[index] with intervals[index+1]
if (index != -1 && intervals[index].end + 1 == intervals[index+1].start) {
intervals[index].end = intervals[index+1].end;
intervals.erase(intervals.begin()+index+1);
}

return;
}

vector<Interval> getIntervals() {
return this->intervals;
}
};``````

• This solution is pretty straight-forward. To `addNum`, the binary search takes `O(log N)` and then to insert the number into the intervals, best case it will take `O(1)` and worst case `O(N)`. So the total time is best `O(log N)`, and worst `O(N + log N)`.

• Python solution with the same idea:

``````class SummaryRanges(object):

def __init__(self):
"""
"""
self.intervals = []

def _binary_search(self, val):
if len(self.intervals) == 0:
return -1
left, right = 0, len(self.intervals) - 1
while left + 1 < right:
mid = left + (right - left) / 2
if self.intervals[mid].start == val:
return mid
elif self.intervals[mid].start > val:
right = mid
else:
left = mid
if self.intervals[right].start <= val:
return right
elif self.intervals[left].start <= val:
return left
return -1

"""
:type val: int
:rtype: void
"""
"""
For a new number val, find the last(biggest) interval
[s,t], such that s <= val. If no such interval exists,
return -1.
"""
index = self._binary_search(val)
if index != -1 and self.intervals[index].end >= val:
return
if index != len(self.intervals) - 1 and self.intervals[index + 1].start == val + 1:
self.intervals[index + 1].start = val
elif index != -1 and val - 1 == self.intervals[index].end:
self.intervals[index].end = val
else:
self.intervals = self.intervals[:index + 1] + [Interval(val, val)] + self.intervals[index + 1:]

if index != -1 and index != len(self.intervals) - 1 and self.intervals[index].end + 1 == self.intervals[index + 1].start:
self.intervals[index].end = self.intervals[index + 1].end
self.intervals = self.intervals[:index + 1] + self.intervals[index + 2:]

def getIntervals(self):
"""
:rtype: List[Interval]
"""
return self.intervals
``````

• I love your solution! I just want to point out that there might be a bug in your solution. When you merge the intervals, you check if `index != -1` but you don't check if `index < intervals.size()`. Although the code still works, that's just because the compiler somehow returns 0 when you access an element out of the vector's bounds. For example, on a vector of size 5, `intervals[10].start` returns 0 instead of crashing. :o So, in the case of addNum(1) then addNum(2), I would expect the code to make [1,1], then make[1,2], then when it gets to the merge intervals code, it'll try to access `intervals[index+1].start`. Index is 0, and size of intervals is 1, so element at index 1, shouldn't exist. I expect it to crash but it doesn't. Thanks for reading!

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