Data Stream as Disjoint Intervals

Hard
2090.

Data Stream as Disjoint Intervals

Data Stream as Disjoint Intervals is a hard coding problem on binary search and ordered set, asked in Amazon and Google interviews.

Non-negative integers arrive one at a time. At any moment, summarise the distinct numbers seen so far as a list of disjoint intervals: each interval [start, end] covers every integer from start to end, and no two intervals touch or overlap (so [1, 2] and [3, 3] would be one interval [1, 3]).

Write the class SummaryRanges:

  • SummaryRanges() starts with no numbers.
  • void addNum(int value) adds value to the stream (it may have been seen before).
  • int[][] getIntervals() returns the summary as a list of [start, end] pairs sorted by start.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"] [[],[4],[],[6],[],[10],[],[5],[],[9],[]]
Output
[null,null,[[4,4]],null,[[4,4],[6,6]],null,[[4,4],[6,6],[10,10]],null,[[4,6],[10,10]],null,[[4,6],[9,10]]]
Explanation
4, 6 and 10 start as separate intervals. 5 joins [4, 4] and [6, 6] into [4, 6]; 9 extends [10, 10] to [9, 10].

Example 2

Input
["SummaryRanges","getIntervals","addNum","addNum","addNum","getIntervals"] [[],[],[10000],[0],[10000],[]]
Output
[null,[],null,null,null,[[0,0],[10000,10000]]]
Explanation
Before any number arrives the summary is empty. Adding 10000 a second time changes nothing.

Constraints

  • 0 <= value <= 10^4
  • At most 3 * 10^4 calls are made in total to addNum and getIntervals
  • At most 10^2 calls are made to getIntervals

Follow-up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the stream?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var SummaryRanges = function() {
    
};

/**
 * @param {number} value
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(value) {
    
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    
};

Sign in to run your own test cases

Sign in

Data Stream as Disjoint Intervals — Problem & Solution

Data Stream as Disjoint Intervals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Data Stream as Disjoint Intervals is a hard coding problem on binary search and ordered set, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Binary Search, Ordered Set
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Non-negative integers arrive one at a time. At any moment, summarise the distinct numbers seen so far as a list of disjoint intervals: each interval [start, end] covers every integer from start to end, and no two intervals touch or overlap (so [1, 2] and [3, 3] would be one interval [1, 3]).

Write the class SummaryRanges:

  • SummaryRanges() starts with no numbers.
  • void addNum(int value) adds value to the stream (it may have been seen before).
  • int[][] getIntervals() returns the summary as a list of [start, end] pairs sorted by start.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"]
[[],[4],[],[6],[],[10],[],[5],[],[9],[]]
Output: [null,null,[[4,4]],null,[[4,4],[6,6]],null,[[4,4],[6,6],[10,10]],null,[[4,6],[10,10]],null,[[4,6],[9,10]]]
Explanation: 4, 6 and 10 start as separate intervals. 5 joins [4, 4] and [6, 6] into [4, 6]; 9 extends [10, 10] to [9, 10].

Example 2

Input: ["SummaryRanges","getIntervals","addNum","addNum","addNum","getIntervals"]
[[],[],[10000],[0],[10000],[]]
Output: [null,[],null,null,null,[[0,0],[10000,10000]]]
Explanation: Before any number arrives the summary is empty. Adding 10000 a second time changes nothing.

Constraints

  • 0 <= value <= 10^4
  • At most 3 * 10^4 calls are made in total to addNum and getIntervals
  • At most 10^2 calls are made to getIntervals

Follow-up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the stream?

Hints for Data Stream as Disjoint Intervals

  1. Hint 1

    Keep the intervals themselves, sorted by start, rather than the raw numbers.

  2. Hint 2

    A new value can only interact with two intervals: the last one starting at or before it, and the first one starting after it. Find them by binary search (or an ordered map's floor and higher entries).

  3. Hint 3

    Four cases: the value is already covered; it is adjacent to both neighbours (merge them); adjacent to one (extend it); or to neither (insert [value, value]).

How to solve Data Stream as Disjoint Intervals

Maintain the summary itself — a sorted list of disjoint, non-adjacent intervals — and update it locally on each addition. Only the interval just before the value and the one just after it can absorb or be merged by the value.

Approach

  1. Let i be the index of the first interval whose start is greater than value; the interval before it, i - 1, is the last one starting at or before value.
  2. If interval i - 1 exists and its end is >= value, the value is already covered — stop.
  3. Let left be whether interval i - 1 ends at value - 1, and right whether interval i starts at value + 1.
  4. Both: set interval i - 1's end to interval i's end and delete interval i. Only left: set interval i - 1's end to value. Only right: set interval i's start to value. Neither: insert [value, value] at position i.
  5. getIntervals() returns the list as it is.

Why it works

The list stays sorted, disjoint and non-adjacent: a covered value changes nothing; otherwise value lies strictly between the end of interval i - 1 and the start of interval i, so only those two can be adjacent to it, and each case joins exactly the intervals that value connects. Every other interval is at least two away from value and is untouched.

Complexity

  • Time — O(log k) to locate plus O(k) for an array insertion or deletion (O(log k) with a balanced ordered map), where k is the number of intervals; getIntervals is O(k)
  • Space — O(k)

Pitfalls

  • Repeated values must not create duplicate intervals — check whether the value is already covered first.
  • Intervals that become adjacent (end + 1 == next start) must be merged; they are not allowed to sit side by side.

Reference solution

Python

from bisect import bisect_right

class SummaryRanges:

    def __init__(self):
        self.starts = []  # disjoint, non-adjacent intervals, sorted
        self.ends = []

    def addNum(self, value: int) -> None:
        s, e = self.starts, self.ends
        i = bisect_right(s, value)  # first interval starting after value
        if i > 0 and e[i - 1] >= value:
            return  # already covered
        left = i > 0 and e[i - 1] == value - 1
        right = i < len(s) and s[i] == value + 1
        if left and right:
            e[i - 1] = e[i]
            del s[i]
            del e[i]
        elif left:
            e[i - 1] = value
        elif right:
            s[i] = value
        else:
            s.insert(i, value)
            e.insert(i, value)

    def getIntervals(self) -> List[List[int]]:
        return [[a, b] for a, b in zip(self.starts, self.ends)]

Java

class SummaryRanges {
    private TreeMap<Integer, Integer> iv = new TreeMap<>(); // start -> end, disjoint and non-adjacent

    public SummaryRanges() {
    }

    public void addNum(int value) {
        Map.Entry<Integer, Integer> lo = iv.floorEntry(value), hi = iv.higherEntry(value);
        if (lo != null && lo.getValue() >= value) return; // already covered
        boolean left = lo != null && lo.getValue() == value - 1;
        boolean right = hi != null && hi.getKey() == value + 1;
        if (left && right) {
            iv.put(lo.getKey(), hi.getValue());
            iv.remove(hi.getKey());
        } else if (left) {
            iv.put(lo.getKey(), value);
        } else if (right) {
            iv.remove(hi.getKey());
            iv.put(value, hi.getValue());
        } else {
            iv.put(value, value);
        }
    }

    public int[][] getIntervals() {
        int[][] out = new int[iv.size()][];
        int k = 0;
        for (Map.Entry<Integer, Integer> e : iv.entrySet()) out[k++] = new int[]{e.getKey(), e.getValue()};
        return out;
    }
}

C++

class SummaryRanges {
    map<int, int> iv; // start -> end, disjoint and non-adjacent
public:
    SummaryRanges() {}

    void addNum(int value) {
        auto hi = iv.upper_bound(value); // first interval starting after value
        auto lo = hi == iv.begin() ? iv.end() : prev(hi);
        if (lo != iv.end() && lo->second >= value) return; // already covered
        bool left = lo != iv.end() && lo->second == value - 1;
        bool right = hi != iv.end() && hi->first == value + 1;
        if (left && right) {
            lo->second = hi->second;
            iv.erase(hi);
        } else if (left) {
            lo->second = value;
        } else if (right) {
            int e = hi->second;
            iv.erase(hi);
            iv[value] = e;
        } else {
            iv[value] = value;
        }
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> out;
        for (auto& p : iv) out.push_back({p.first, p.second});
        return out;
    }
};

JavaScript

var SummaryRanges = function() {
    this.starts = []; // disjoint, non-adjacent intervals, sorted
    this.ends = [];
};

SummaryRanges.prototype.addNum = function(value) {
    var s = this.starts, e = this.ends;
    var lo = 0, hi = s.length; // first interval starting after value
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (s[mid] <= value) lo = mid + 1; else hi = mid;
    }
    var i = lo;
    if (i > 0 && e[i - 1] >= value) return; // already covered
    var left = i > 0 && e[i - 1] === value - 1;
    var right = i < s.length && s[i] === value + 1;
    if (left && right) { e[i - 1] = e[i]; s.splice(i, 1); e.splice(i, 1); }
    else if (left) e[i - 1] = value;
    else if (right) s[i] = value;
    else { s.splice(i, 0, value); e.splice(i, 0, value); }
};

SummaryRanges.prototype.getIntervals = function() {
    var out = [];
    for (var i = 0; i < this.starts.length; i++) out.push([this.starts[i], this.ends[i]]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 189 binary search problems · the whole catalogue

Learn the technique: Binary Search