Data Stream as Disjoint Intervals
HardPrompt
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 integervalueto the stream.int[][] getIntervals()Returns a summary of the integers in the stream currently as a list of disjoint intervals[starti, endi]. The answer should be sorted bystarti.
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]]
Constraints:
0 <= value <= 104- At most
3 * 104calls will be made toaddNumandgetIntervals. - At most
102calls will be made togetIntervals.
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?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple strategy: collect all unique numbers from the stream and process them only when getIntervals() is called. A HashSet is used to store the numbers, which makes the addNum operation very fast.
Algorithm
- Data Structure: Use a
HashSet<Integer>to store the numbers from the data stream. This automatically handles duplicates. addNum(value):- Add the
valueto theHashSet. This is an O(1) average time operation.
- Add the
getIntervals():- If the set is empty, return an empty array.
- Create a
Listfrom the elements of theHashSet. - Sort the list in ascending order. This is the most time-consuming step, taking O(N log N) time, where N is the number of unique numbers.
- Initialize an empty list of intervals,
result. - Iterate through the sorted list to form intervals. Keep track of the
startandendof the current interval. - If the current number is
end + 1, it's part of the current interval, so updateend. - If it's not consecutive, the previous interval
[start, end]is complete. Add it toresultand start a new interval with the current number. - After the loop, add the last formed interval to
result. - Convert the
resultlist to a 2D array and return it.
Walkthrough
In this method, we prioritize making the addNum operation as fast as possible. We use a HashSet to store all unique numbers encountered in the stream. Adding a number is an O(1) operation on average.
The main work is deferred to the getIntervals method. When it's called, we first convert the set of numbers into a list, then sort it. This sorting step takes O(N log N) time, where N is the number of unique numbers seen so far. After sorting, we can iterate through the list in a single pass (O(N) time) to identify and merge consecutive numbers into disjoint intervals. The overall performance is thus dominated by the sorting step.
import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Set; class SummaryRanges { private Set<Integer> numbers; public SummaryRanges() { numbers = new HashSet<>(); } public void addNum(int value) { numbers.add(value); } public int[][] getIntervals() { if (numbers.isEmpty()) { return new int[0][]; } List<Integer> sortedNums = new ArrayList<>(numbers); Collections.sort(sortedNums); List<int[]> intervals = new ArrayList<>(); int start = sortedNums.get(0); int end = sortedNums.get(0); for (int i = 1; i < sortedNums.size(); i++) { int current = sortedNums.get(i); if (current == end + 1) { end = current; } else { intervals.add(new int[]{start, end}); start = current; end = current; } } intervals.add(new int[]{start, end}); return intervals.toArray(new int[intervals.size()][]); }}Complexity
Time
`addNum`: O(1) on average. `getIntervals`: O(N log N), where N is the number of unique integers. The sorting step is the bottleneck.
Space
O(N), where N is the number of unique integers added to the stream. This space is used to store the numbers in the `HashSet`.
Trade-offs
Pros
The
addNumoperation is very fast, with an average time complexity of O(1).The implementation is straightforward and easy to understand.
Cons
getIntervals()has a high time complexity of O(N log N), which can be slow if N is large.This approach recomputes all intervals from scratch every time
getIntervals()is called, which is inefficient if this method is called frequently.
This approach leverages the small and fixed range of the input values. By using a boolean array (or a bitset) to mark which numbers have been seen, we can make both addNum and getIntervals operations very fast and independent of the number of elements in the stream.
Algorithm
- Data Structure: Use a boolean array
seenof size10001, given the constraint0 <= value <= 10000.seen[i]will betrueif the numberihas been added to the stream. addNum(value):- Set
seen[value] = true. This is an O(1) operation.
- Set
getIntervals():- Initialize an empty list
intervalsto store the results. - Iterate through the
seenarray with an indexifrom 0 to 10000. - If
seen[i]istrue, it signifies the start of an interval. - Set
start = i. - Find the end of this interval by advancing a second pointer
jfromias long asjis within bounds andseen[j]istrue. - The interval is
[start, j - 1]. Add it to theintervalslist. - Continue the main loop by setting
i = jto avoid re-checking the numbers within the interval just found. - If
seen[i]isfalse, simply incrementi. - Convert the
intervalslist to a 2D array and return.
- Initialize an empty list
Walkthrough
Since the input values are non-negative and capped at 10000, we can allocate a boolean array seen of size 10001. Each index in this array corresponds to a number.
For addNum(value), we simply perform a direct lookup and set the corresponding flag: seen[value] = true. This is an O(1) operation.
For getIntervals(), we can iterate through the entire seen array once. When we find an index i where seen[i] is true, we know this is the start of an interval. We then scan forward to find the end of this contiguous block of true values. This gives us one disjoint interval. We then continue our scan from where the interval ended. The total time for this is proportional to the size of the boolean array, which is constant.
import java.util.ArrayList;import java.util.List; class SummaryRanges { private boolean[] seen; public SummaryRanges() { // Constraints: 0 <= value <= 10^4 seen = new boolean[10001]; } public void addNum(int value) { seen[value] = true; } public int[][] getIntervals() { List<int[]> intervals = new ArrayList<>(); int i = 0; while (i < seen.length) { if (seen[i]) { int start = i; int j = i; while (j < seen.length && seen[j]) { j++; } intervals.add(new int[]{start, j - 1}); i = j; } else { i++; } } return intervals.toArray(new int[intervals.size()][]); }}Complexity
Time
`addNum`: O(1). `getIntervals`: O(M), where M is the maximum possible value. This is constant time relative to the number of elements in the stream.
Space
O(M), where M is the maximum possible value of an input number (10001 in this case). The space is constant and does not depend on the number of calls.
Trade-offs
Pros
Both
addNumandgetIntervalshave constant time complexity with respect to the number of elements added.The implementation is relatively simple.
Cons
The space complexity is O(M), where M is the maximum possible value. This is not feasible if the range of values is very large.
The
getIntervalsmethod always iterates through the entire range of possible values (M), which can be inefficient if the number of actual intervals (K) is much smaller than M.
This is the most efficient and scalable approach, especially for the follow-up scenario where the number of disjoint intervals is small. It maintains the intervals directly in a sorted map (TreeMap), allowing for efficient insertion and merging.
Algorithm
- Data Structure: Use a
TreeMap<Integer, int[]>where the key is the start of an interval and the value is the interval itself (int[]{start, end}).TreeMapkeeps the intervals sorted by their start times and provides efficient logarithmic time lookups. addNum(value):- Find the interval whose start is just lower than or equal to
value(lowerKey) and the interval whose start is just higher thanvalue(higherKey). These are O(log K) operations. - Check if
valueis already covered by an existing interval. IflowerKeyexists and its interval's end is greater than or equal tovalue, do nothing. - Determine if the new
valuecan merge with the lower interval (lowerInterval.end + 1 == value) and/or the higher interval (higherKey == value + 1). - Case 1: Merge with both. If it merges with both lower and higher intervals, extend the lower interval to cover the higher one's end, and remove the higher interval from the map.
- Case 2: Merge with lower only. Extend the lower interval's end to
value. - Case 3: Merge with higher only. Remove the higher interval and insert a new one starting at
valueand ending at the higher interval's original end. - Case 4: No merge. Insert a new interval
[value, value]into the map.
- Find the interval whose start is just lower than or equal to
getIntervals():- The
TreeMap's values view (treeMap.values()) provides a collection of the intervals, already sorted by their start times. Convert this collection to a 2D array. This takes O(K) time.
- The
Walkthrough
This approach directly manages the list of disjoint intervals. By storing them in a TreeMap, we can leverage its ability to keep keys (interval start points) sorted and perform efficient lookups, insertions, and deletions in O(log K) time, where K is the current number of disjoint intervals.
When addNum(value) is called, we first check if the value is already contained within an existing interval. If not, we look for adjacent intervals. We find the interval that ends just before value and the one that starts just after value. Based on whether value is consecutive to one or both of these, we perform a merge.
- If
valueconnects two existing intervals, we merge them into one. - If it's adjacent to only one, we extend that interval.
- If it's isolated, we create a new interval of
[value, value].
Each addNum call involves a few O(log K) operations on the TreeMap. The getIntervals method is very efficient as it just needs to dump the values from the TreeMap into an array, which takes O(K) time.
import java.util.TreeMap; class SummaryRanges { private TreeMap<Integer, int[]> treeMap; public SummaryRanges() { treeMap = new TreeMap<>(); } public void addNum(int value) { if (treeMap.containsKey(value)) { return; } // Find intervals that are just lower and higher than value Integer lowerKey = treeMap.lowerKey(value); Integer higherKey = treeMap.higherKey(value); // Check if value is already covered by an interval starting at or before value if (lowerKey != null && treeMap.get(lowerKey)[1] >= value) { return; } boolean mergeWithLower = (lowerKey != null && treeMap.get(lowerKey)[1] + 1 == value); boolean mergeWithHigher = (higherKey != null && higherKey == value + 1); if (mergeWithLower && mergeWithHigher) { // Merge lower and higher intervals int[] lowerInterval = treeMap.get(lowerKey); int[] higherInterval = treeMap.get(higherKey); lowerInterval[1] = higherInterval[1]; treeMap.remove(higherKey); } else if (mergeWithLower) { // Extend lower interval treeMap.get(lowerKey)[1] = value; } else if (mergeWithHigher) { // Extend higher interval by creating a new one and removing the old int[] higherInterval = treeMap.remove(higherKey); treeMap.put(value, new int[]{value, higherInterval[1]}); } else { // Add a new interval treeMap.put(value, new int[]{value, value}); } } public int[][] getIntervals() { return treeMap.values().toArray(new int[treeMap.size()][]); }}Complexity
Time
`addNum`: O(log K), where K is the number of disjoint intervals. `getIntervals`: O(K).
Space
O(K), where K is the number of disjoint intervals. This is optimal as we must store the intervals.
Trade-offs
Pros
Highly efficient
addNumoperation with O(log K) time complexity.Efficient
getIntervalswith O(K) time complexity.Space complexity O(K) is optimal, as it only stores the necessary intervals.
It's a general solution that works for any range of input values, not just small ones.
Perfectly addresses the follow-up question about frequent merges and a small number of intervals.
Cons
The implementation is more complex than the other approaches due to handling multiple merge cases.
There is a slight overhead for
addNum(O(log K)) compared to O(1) approaches, though it's negligible in practice.
Solutions
Solution
class SummaryRanges { private TreeMap < Integer , int []> mp ; public SummaryRanges () { mp = new TreeMap <>(); } public void addNum ( int val ) { Integer l = mp . floorKey ( val ); Integer r = mp . ceilingKey ( val ); if ( l != null && r != null && mp . get ( l )[ 1 ] + 1 == val && mp . get ( r )[ 0 ] - 1 == val ) { mp . get ( l )[ 1 ] = mp . get ( r )[ 1 ]; mp . remove ( r ); } else if ( l != null && val <= mp . get ( l )[ 1 ] + 1 ) { mp . get ( l )[ 1 ] = Math . max ( val , mp . get ( l )[ 1 ]); } else if ( r != null && val >= mp . get ( r )[ 0 ] - 1 ) { mp . get ( r )[ 0 ] = Math . min ( val , mp . get ( r )[ 0 ]); } else { mp . put ( val , new int [] { val , val }); } } public int [][] getIntervals () { int [][] res = new int [ mp . size ()][ 2 ]; int i = 0 ; for ( int [] range : mp . values ()) { res [ i ++] = range ; } return res ; } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * int[][] param_2 = obj.getIntervals(); */class SummaryRanges { private: map < int , vector < int >> mp ; public: SummaryRanges () { } void addNum ( int val ) { auto r = mp . upper_bound ( val ); auto l = r == mp . begin () ? mp . end () : prev ( r ); if ( l != mp . end () && r != mp . end () && l -> second [ 1 ] + 1 == val && r -> second [ 0 ] - 1 == val ) { l -> second [ 1 ] = r -> second [ 1 ]; mp . erase ( r ); } else if ( l != mp . end () && val <= l -> second [ 1 ] + 1 ) l -> second [ 1 ] = max ( val , l -> second [ 1 ]); else if ( r != mp . end () && val >= r -> second [ 0 ] - 1 ) r -> second [ 0 ] = min ( val , r -> second [ 0 ]); else mp [ val ] = { val , val }; } vector < vector < int >> getIntervals () { vector < vector < int >> res ; for ( auto & range : mp ) res . push_back ( range . second ); return res ; } }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e # better and easier, manual filter() via while # I like this one the most class SummaryRanges : def __init__ ( self ): self . intervals = [] def addNum ( self , val : int ) -> None : new_interval = [ val , val ] merged_intervals = [] i = 0 # before overlap part while i < len ( self . intervals ) and self . intervals [ i ][ 1 ] < val - 1 : merged_intervals . append ( self . intervals [ i ]) i += 1 # process overlap while i < len ( self . intervals ) and self . intervals [ i ][ 0 ] <= val + 1 : new_interval [ 0 ] = min ( new_interval [ 0 ], self . intervals [ i ][ 0 ]) new_interval [ 1 ] = max ( new_interval [ 1 ], self . intervals [ i ][ 1 ]) i += 1 merged_intervals . append ( new_interval ) # after overlap part while i < len ( self . intervals ): merged_intervals . append ( self . intervals [ i ]) i += 1 # also passed OJ, instead of while loop: # merged_intervals.extend(self.intervals[i:]) self . intervals = merged_intervals def getIntervals ( self ) -> List [ List [ int ]]: return self . intervals ############ class SummaryRanges : # passed OJ, optimized below solution def __init__ ( self ): self . intervals = [] def insert ( self , newInterval : List [ int ]): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ intervals = self . intervals # print intervals if not intervals : intervals . append ( newInterval ) return s , e = newInterval [ 0 ], newInterval [ 1 ] left = list ( filter ( lambda x : x [ 1 ] + 1 < newInterval [ 0 ], intervals )) right = list ( filter ( lambda x : x [ 0 ] - 1 > newInterval [ 1 ], intervals )) if left + right != intervals : s = min ( intervals [ len ( left )][ 0 ], s ) e = max ( intervals [ ~ len ( right )][ 1 ], e ) # +1 or -1 check: included in lambda's '+1<' and '-1>' self . intervals = left + [ [ s , e ] ] + right def addNum ( self , val : int ) -> None : self . insert ([ val , val ]) def getIntervals ( self ) -> List [ List [ int ]]: return self . intervals ############ class SummaryRanges : # above is optimized version def __init__ ( self ): self . intervals = [] def insert ( self , newInterval : List [ int ]): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ intervals = self . intervals # print intervals if not intervals : intervals . append ( newInterval ) return s , e = newInterval [ 0 ], newInterval [ 1 ] left = list ( filter ( lambda x : x [ 1 ] < newInterval [ 0 ], intervals )) right = list ( filter ( lambda x : x [ 0 ] > newInterval [ 1 ], intervals )) # print left, right, (s, e) if left + right != intervals : s = min ( intervals [ len ( left )][ 0 ], s ) e = max ( intervals [ ~ len ( right )][ 1 ], e ) newIntv = [ s , e ] # merging piece is different from above solution if left and left [ - 1 ][ 1 ] + 1 == s : newIntv [ 0 ] = left [ - 1 ][ 0 ] left = left [: - 1 ] # cut out last one, which is merged with newIntv if right and right [ 0 ][ 0 ] - 1 == e : newIntv [ 1 ] = right [ 0 ][ 1 ] right = right [ 1 :] # cut out first one, which is merged with newIntv self . intervals = left + [ newIntv ] + right def addNum ( self , val : int ) -> None : self . insert ([ val , val ]) def getIntervals ( self ) -> List [ List [ int ]]: return self . intervals # Your SummaryRanges object will be instantiated and called as such: # obj = SummaryRanges() # obj.addNum(val) # param_2 = obj.getIntervals() ############ ''' >>> mp = SortedDict() >>> mp.bisect_right(3) 0 >>> mp = SortedDict() >>> mp[1]=[1,1] >>> mp[3]=[3,3] >>> mp[5]=[5,5] >>> >>> mp SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]}) >>> mp.bisect_right(-10) 0 >>> mp.bisect_right(100) 3 >>> mp.bisect_right(2) 1 >>> mp.values() SortedValuesView(SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]})) >>> list(mp.values()) [[1, 1], [3, 3], [5, 5]] >>> ''' from sortedcontainers import SortedDict class SummaryRanges : def __init__ ( self ): self . mp = SortedDict () def addNum ( self , val : int ) -> None : n = len ( self . mp ) ridx = self . mp . bisect_right ( val ) lidx = n if ridx == 0 else ( ridx - 1 ) # n is similar to java treemap returning null keys = self . mp . keys () values = self . mp . values () if ( lidx != n and ridx != n and values [ lidx ][ 1 ] + 1 == val and values [ ridx ][ 0 ] - 1 == val ): self . mp [ keys [ lidx ]][ 1 ] = self . mp [ keys [ ridx ]][ 1 ] self . mp . pop ( keys [ ridx ]) elif lidx != n and val <= values [ lidx ][ 1 ] + 1 : # <= because, it could be [1 -> 10], and new add is [5,5] self . mp [ keys [ lidx ]][ 1 ] = max ( val , self . mp [ keys [ lidx ]][ 1 ]) elif ridx != n and val >= values [ ridx ][ 0 ] - 1 : self . mp [ keys [ ridx ]][ 0 ] = min ( val , self . mp [ keys [ ridx ]][ 0 ]) else : self . mp [ val ] = [ val , val ] def getIntervals ( self ) -> List [ List [ int ]]: return list ( self . mp . values ()) # # Your SummaryRanges object will be instantiated and called as such: # # obj = SummaryRanges() # # obj.addNum(val) # # param_2 = obj.getIntervals()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.