Leetcode 352: Data Stream as Disjoint Intervals

dume0011
2 min readFeb 7, 2021

--

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

Problem Analysis:

A simple method is put integers to a set, then iterate data in set to construct the interval list. See code example 1 bellow.

We can construct intervals with vector, when add new integer, insert the integer in proper interval, and merge interval when needed. See code example 2 bellow.

Solution 1:

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

}

void addNum(int val) {
data_.insert(val);
}

vector<vector<int>> getIntervals() {
vector<vector<int>> res;
int start = -1;
int end = -1;
for (const auto& item: data_) {
if (start == -1) {
start = item;
end = item;
} else if (item == end + 1) {
end = item;
} else {
res.push_back({start, end});
start = end = item;
}
}

if (start != -1) res.push_back({start, end});

return res;
}
private:
set<int> data_;
};

Solution 2:

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

}

void addNum(int val) {
vector<int> interval{val, val};
if (data_.empty()) {
data_.push_back(interval);
return;
}
int i = 0;
for (; i < data_.size(); ++i)
if (data_[i][0] > val) break;
if (i == 0) {
if (val + 1 == data_[i][0]) data_[i][0] = val;
else data_.insert(data_.begin(), interval);
} else {
if (i == data_.size()) {
if (data_[i - 1][1] + 1 == val) data_[i - 1][1] = val;
else if (data_[i - 1][1] < val) data_.push_back(interval);
} else {
if (data_[i - 1][1] < val) {
if (data_[i - 1][1] + 1 == val) {
if (data_[i][0] == val + 1) {
data_[i - 1][1] = data_[i][1];
data_.erase(data_.begin() + i);
} else {
data_[i - 1][1] = val;
}
} else {
if (data_[i][0] == val + 1) data_[i][0] = val;
else data_.insert(data_.begin() + i, interval);
}
}
}
}
}

vector<vector<int>> getIntervals() {
return data_;
}
private:
vector<vector<int>> data_;
};

The two methods’s space complexity are O(n), the first time complexity: addNum is O(lgn), getIntervals is O(n), the second time complexity: addNum is O(n), getIntervals is O(1)

--

--