235. Stream to Ranges

HardDesignData StreamOrdered SetIntervals4 hints
RPby Rohit Parihar

A turnstile counts visitors by badge number. Badge numbers arrive one at a time, in any order, and the same number may arrive again. At any moment the gate manager wants a compact summary: the set of badge numbers seen so far written as a list of ranges [start, end], where both ends are included.

Implement the class StreamRanges:

  • StreamRanges() starts with no numbers.
  • void addNum(int value) records one more badge number.
  • int[][] getIntervals() returns the numbers seen so far as disjoint ranges sorted by start. Consecutive numbers must be merged into one range: after seeing 4 and 6, adding 5 turns [4,4],[6,6] into [4,6]. No two returned ranges may touch or overlap.

Up to 10,000 numbers may be added and the summary may be requested many times, so avoid rebuilding it from scratch on every call.

Example 1

Input:
operations = ["StreamRanges","addNum","addNum","getIntervals","addNum","getIntervals"]arguments = [[],[7],[9],[],[8],[]]
Output:
[null,null,null,[[7,7],[9,9]],null,[[7,9]]]
Explanation:

Outputs: [null, null, null, [[7,7],[9,9]], null, [[7,9]]]. Adding 8 joins the two ranges because it touches both.

Example 2

Input:
operations = ["StreamRanges","addNum","addNum","addNum","getIntervals","addNum","addNum","getIntervals","addNum","getIntervals"]arguments = [[],[2],[3],[10],[],[5],[4],[],[4],[]]
Output:
[null,null,null,null,[[2,3],[10,10]],null,null,[[2,5],[10,10]],null,[[2,5],[10,10]]]
Explanation:

Outputs: [null, null, null, null, [[2,3],[10,10]], null, null, [[2,5],[10,10]], null, [[2,5],[10,10]]]. Adding 5 creates [5,5]; adding 4 bridges [2,3] and [5,5]. Adding 4 again changes nothing.

Constraints

0 ≤ value ≤ 104
At most 3 × 104 calls to addNum and getIntervals in total

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) search per addNum, O(k) per getIntervals
Space
O(k)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.