352. Data Stream as Disjoint Intervals

Posted on 3 mins read

1. Description

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

  • SummaryRanges() Initializes the object with an empty stream.
  • void addNum(int value) Adds the integer value to the stream.
  • int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [$start_i$, $end_i$]. The answer should be sorted by $start_i$.

2. Example

Example 1:
Input
[“SummaryRanges”, “addNum”, “getIntervals”, “addNum”, “getIntervals”, “addNum”, “getIntervals”, “addNum”, “getIntervals”, “addNum”, “getIntervals”]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1); // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3); // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

3. Constraints

  • 0 <= value <= $10^4$
  • At most $3 * 10^4$ calls will be made to addNum and getIntervals.

4. Follow Up

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

5. Solutions

Small Range

n is the number of function calls

class SummaryRanges {
private:
    // the range of value is [0, 10^4]
    // so it's possible to just assign the array to store every value
    array<int, 10001> values;
    int min_border;
    int max_border;

public:
    SummaryRanges() {
        // Time complexity: O(1)
        // Space complexity: O(10000)
        min_border = INT_MAX;
        max_border = 0;
    }

    void addNum(int value) {
        // Time complexity: O(1)
        // Space complexity: O(1)
        values[value] = 1;

        min_border = min(min_border, value);
        max_border = max(max_border, value);
    }

    vector<vector<int>> getIntervals() {
        // Time complexity: O(10000)
        // Space complexity: O(1)
        vector<vector<int>> result;
        for (int i = min_border, j = 0; i <= max_border; ++i) {
            if (values[i] == 1) {
                j = i;
                while (values[j] == 1) {
                    ++j;
                }
                result.emplace_back(vector<int>{i, j - 1});
                i = j;
            }
        }

        return result;
    }
};

Ordered Set

n is the number of function calls

class SummaryRanges {
    set<int> values;

public:
    SummaryRanges() {
        // Time complexity: O(1)
        // Space complexity: O(1)
    }

    void addNum(int value) {
        // Time complexity: O(logn)
        // Space complexity: O(n)
        values.insert(value);
    }

    vector<vector<int>> getIntervals() {
        // Time complexity: O(n)
        // Space complexity: O(1)
        if (values.empty()) {
            return {};
        }
        vector<vector<int>> intervals;
        int left = -1, right = -1;
        for (int value : values) {
            if (left < 0) {
                left = right = value;
            } else if (value == right + 1) {
                right = value;
            } else {
                intervals.push_back({left, right});
                left = right = value;
            }
        }
        intervals.push_back({left, right});
        return intervals;
    }
};

Ordered Map

n is the number of function calls

class SummaryRanges {
    map<int, int> intervals;

public:
    SummaryRanges() {
        // Time complexity: O(1)
        // Space complexity: O(1)
    }

    void addNum(int value) {
        // Time complexity: O(logn)
        // Space complexity: O(n)
        int left = value, right = value;
        auto small_entry = intervals.upper_bound(value);
        if (small_entry != intervals.begin()) {
            auto max_entry = small_entry;
            --max_entry;
            if (max_entry->second >= value) {
                return;
            }
            if (max_entry->second == value - 1) {
                left = max_entry->first;
            }
        }
        if (small_entry != intervals.end() && small_entry->first == value + 1) {
            right = small_entry->second;
            intervals.erase(small_entry);
        }
        intervals[left] = right;
    }

    vector<vector<int>> getIntervals() {
        // Time complexity: O(n)
        // Space complexity: O(1)
        vector<vector<int>> answer;
        for (const auto &p : intervals) {
            answer.push_back({p.first, p.second});
        }
        return answer;
    }
};
comments powered by Disqus