# C++ solution with vector beats 96.52%

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

}

int idx = find(val);
if (idx == -2) return; // val already exists
if (idx == -1) {
if (!data.empty() && data[0].start == val + 1) {
data[0].start--;
return;
}

Interval i(val, val);
data.insert(data.begin(), i);
}
else {
bool left = false, right = false;
if (data[idx].end == val - 1) left = true;
if (idx + 1 < data.size() && data[idx + 1].start == val + 1) right = true;

if (left && right) {
data[idx].end = data[idx + 1].end;
data.erase(data.begin() + idx + 1);
}
else if (left) data[idx].end++;
else if (right) data[idx + 1].start--;
else {
Interval i(val, val);
data.insert(data.begin() + idx + 1, i);
}
}
}

vector<Interval> getIntervals() {
return data;
}

private:
vector<Interval> data;

int find(int val) { // find the last idx such that data[idx].end < val
if (data.empty()) return -1;
int lo = 0, hi = data.size() - 1, mid;
while (lo < hi) {
mid = lo + (hi - lo + 1) / 2;
if (val >= data[mid].start && val <= data[mid].end) return -2;
if (data[mid].end > val) hi = mid - 1;
else lo = mid;
}

if (val >= data[lo].start && val <= data[lo].end) return -2;
if (data[lo].end > val) return -1;
else return lo;
}
};
``````

• I guess the problem description should clarify which method is called more often.

You solution has O(n) addNum but O(1) getIntervals

while the normal BST & LinkedList solution has O(lgn) addNum and O(n) getIntervals