Problem Description

This LeetCode problem involves writing a class called SummaryRanges that is designed to keep track of a stream of non-negative integers and provide a summarized view of the data in the form of disjoint intervals. The class should support two operations:

1. addNum(value): This method takes a non-negative integer value and adds it to the stream.
2. getIntervals(): This method returns the current summary of the stream as a list of disjoint intervals [start_i, end_i]. Each interval represents a sequence of consecutive numbers that have been added to the stream. The list of intervals is sorted based on the start_i of each interval.

The goal of SummaryRanges is to condense the stream of integers into as few intervals as possible by merging consecutive numbers together.

Intuition

To solve this problem, one needs to efficiently manage intervals of consecutive numbers with operations to insert a number into the stream and then update and merge these intervals. The key challenge is handling numbers that might need to merge with existing intervals when they fit just right before the start, after the end, or in between two existing intervals.

To address this efficiently, we can use a data structure that maintains the intervals in a sorted order to easily locate where the new number fits relative to existing intervals. This would simplify operations for finding, adding, or merging intervals. A SortedDict, which is a dictionary that keeps its keys sorted, can be used for this purpose. Each key is an integer from the data stream, and the corresponding value is an interval [start, end] representing consecutive numbers.

Here is the intuition behind handling the addition of a new number, val, to the stream:

1. Check if val can merge with an existing interval on its left or right or if it fills a gap between two intervals:

   • If val is just after the end of one interval and just before the start of the next, we merge these two intervals.
   • If val is just after the end of an existing interval but not close enough to the next interval, we extend the existing interval to include val.
   • Similarly, if val is just before the start of an existing interval but not close enough to the previous interval, we adjust the start of this interval to include val.

2. If val does not fit next to or between existing intervals, we create a new interval [val, val].

For getting the intervals, since we maintain a sorted dictionary where each interval is stored as values and the keys are the starting points of each interval, we simply return these values.

The provided solution uses this approach with a SortedDict to ensure that we can quickly locate adjacent intervals and merge intervals or adjust their boundaries as necessary when a new number is added.

Learn more about Binary Search patterns.

Solution Approach

The implementation of the SummaryRanges class utilizes a SortedDict from the sortedcontainers module in Python. A SortedDict keeps keys in a sorted order, which is vital for efficient interval management in this problem.

__init__ Method:

The constructor initializes a SortedDict named self.mp. This will store the intervals where the keys will be the start of the intervals.

addNum Method:

This method handles the addition of a new number, val, to the stream and updates the intervals accordingly:

1. We start by determining the position (right index ridx) of the value with respect to the sorted keys using self.mp.bisect_right(val). This gives us the index of the first key that is greater than val (if any). Similarly, we calculate the left index (lidx) which is just ridx - 1 if val is not the first number to be inserted or n (the length of the SortedDict) if ridx is 0.

2. With keys and values of the SortedDict extracted, we use the indices to find the adjacent intervals (if they exist).

3. We check if the new value val can merge with adjacent intervals or if it belongs to a new, separate interval:

   • If the new value val is in between two existing intervals and can merge them (values[lidx][1] + 1 == val and values[ridx][0] - 1 == val), we extend the left interval to cover the right one and remove the right interval.
   • If the new value val can be appended to the end of the left interval (val <= values[lidx][1] + 1), we update the end of this interval.
   • If the new value val can be prepended to the start of the right interval (val >= values[ridx][0] - 1), we update the start of this interval.
   • If none of the above conditions are met, val creates its own interval [val, val].

4. We then insert the new interval or update the existing intervals in the SortedDict accordingly.

getIntervals Method:

This is a straightforward method that returns all values (which are the intervals) in the SortedDict. Since the SortedDict maintains the intervals in ascending order based on their starting points, no further sorting is needed.

Overall, the algorithm effectively maintains and manipulates intervals, using the fast lookup and ordered nature of the SortedDict. The choice of data structure greatly simplifies the complexity of adding and merging intervals while keeping the stream data summarized efficiently.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Assume we have an instance of SummaryRanges and we perform the following operations:

1. addNum(1)
2. addNum(3)
3. getIntervals() - Should return [[1, 1], [3, 3]]
4. addNum(2)
5. getIntervals() - Should return [[1, 3]]

Here's what happens internally with each operation:

After operation 1: addNum(1)

• There are no existing intervals.
• val = 1 creates a new interval [1, 1].
• self.mp now stores {1: [1, 1]}.

After operation 2: addNum(3)

• Keys in self.mp are [1].
• val = 3 does not fit with the existing interval [1, 1] as it is not consecutive.
• A new interval [3, 3] is created since it is separate.
• self.mp now stores {1: [1, 1], 3: [3, 3]}.

After operation 3: getIntervals()

• The getIntervals method is called.
• We simply return the values of self.mp as a list: [[1, 1], [3, 3]].

After operation 4: addNum(2)

• Keys in self.mp are [1, 3].
• val = 2 is checked against the intervals.
• val = 2 fits between the intervals [1, 1] and [3, 3] and can merge them since 1 + 1 = 2 = 3 - 1.
• We extend the left interval to [1, 3] and remove the interval [3, 3].
• self.mp now stores {1: [1, 3]}.

After operation 5: getIntervals()

• The getIntervals method is called once again.
• We simply return the values of self.mp as a list: [[1, 3]].

In conclusion, as shown in the example, the SummaryRanges class efficiently manages the addition and merging of intervals. The addNum method updates the SortedDict as required, with the main logic focused on checking if the new value can be merged with existing intervals or if it forms a new interval. The getIntervals method provides the current summarized view as ordered intervals. The effective use of SortedDict dramatically simplifies complex interval logic and ensures efficient manipulation of the data stream.

Solution Implementation

Time and Space Complexity

Time Complexity

The addNum function:

• bisect_right: O(logN) where N is the number of existing intervals in self.mp. This operation performs a binary search.
• Update operations: O(1) for basic integer operations.
• pop: O(logN) because when popping from a sorted dictionary, it maintains the order. Hence, the time complexity for addNum is O(logN) per operation due to the binary search and potential pop operations.

The getIntervals function simply returns the values of the sorted dictionary:

• This operation is O(N) because it constructs a list from the values stored in mp.

Space Complexity

The main space usage in SummaryRanges comes from the sorted dictionary self.mp:

• For addNum: Additional space complexity is O(1) because it stores the interval as a pair of integers only when a new interval is created or extended.
• The SortedDict self.mp can have at most N elements if no intervals overlap, where N is the total number of times addNum is called. Hence, space complexity is O(N) for self.mp.
• For getIntervals: O(N) to store the output list.

Therefore, the overall space complexity is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.