Leetcode 352. Data Stream as Disjoint Intervals

Problem Explanation

In this problem, we are given a stream of non-negative integers, and our task is to convert this stream of individual integers into a list of disjoint intervals.

For instance, if the stream of integers is: 1, 3, 7, 2, 6, our output should organize these into disjoint intervals like so: [1, 1], [3, 3], [7, 7], [1, 3], [6, 7]. We can note that every time we have a new integer that can't fit into existing intervals, we create a new interval, but if the integer can be added into an existing interval or merge two intervals, we update that interval accordingly.

Solution Explanation

The approach to solving this problem uses a map data structure and specifically the TreeMap in Java, which is sorted according to the natural ordering of its keys. For every new number from the stream, we check if it can be part of an existing interval or if it can merge two existing intervals. If not, we create a new interval in the map. We can achieve this through the use of the lowerKey (maximum key less than given key) and higherKey (minimum key greater than given key) methods to check the intervals immediately before and after the current number. The TreeMap guarantees that these intervals are the closest to the current number and thus no other intervals will overlap with it.

Let's illustrate this with an example:

• stream: 1, 3, 7, 2, 6

At the start, our TreeMap is empty. After input 1, it becomes:

1
2
31: [1, 1]

Then, after input 3, we add another interval:

1
2
31: [1, 1]
43: [3, 3]

After input 7, we get:

1
2
31: [1, 1]
43: [3, 3]
57: [7, 7]

For input 2, we can merge it with intervals [1,1] and [3,3], so we update the interval [1,1] to become [1,3] and remove [3,3]:

1
2
31: [1, 3]
47: [7, 7]

Finally, with input 6, we can also merge it with interval [7, 7] to form a new interval [6, 7] and then adjust our TreeMap to look like this:

1
2
31: [1, 3]
46: [6, 7]

And that's our final set of intervals.

Now, let's jump into the coding solution, making sure that we cover Python, Java, JavaScript, C++, and C#. Use the comments as indications of how each piece of code is translating the approach into syntax.

Python Solution

Python does not have an inbuilt TreeMap functionality as is the case with Java. A handy alternative is to use the SortedDict data structure available in the sortedcontainers library, which behaves in a similar way.

1
2python
3from sortedcontainers import SortedDict
4
5class SummaryRanges:
6
7    def __init__(self):
8        """
9        Initialize your data structure here.
10        """
11        self.intervals = SortedDict()
12
13    def addNum(self, val: int) -> None:
14        keys = self.intervals.keys()
15        keys_length = len(keys)
16        l = self.intervals.bisect_left(val)
17        if l != 0 and self.intervals.peekitem(l - 1)[1][1] + 1 >= val:
18            l -= 1
19        if l != keys_length and keys[l] - 1 <= val:
20            r = self.intervals.peekitem(l)[1][1]
21            if l != 0 and self.intervals.peekitem(l - 1)[1][1] + 1 >= val:
22                l -= 1
23            self.intervals[keys[l]] = [keys[l], max(val, r)]
24        else:
25            self.intervals[val] = [val, val]
26        for i, key in enumerate(list(self.intervals.keys())[l:]):
27            if self.intervals.peekitem(i + l + 1)[1][0] > self.intervals.peekitem(i + l)[1][1] + 1:
28                return
29            else:
30                right_bound = self.intervals.peekitem(i + l + 1)[1][1]
31                self.intervals[keys[l]] = [keys[l], right_bound]
32                self.intervals.pop(keys[i + l + 1])
33
34    def getIntervals(self) -> list[list[int]]:
35        return list(self.intervals.values())

Java Solution

Java has great TreeMap functionality which we can use directly to solve the problem.

1
2java
3import java.util.*;
4
5class SummaryRanges {
6
7    private TreeMap<Integer, int[]> treeMap;
8
9    /** Initialize your data structure here. */
10    public SummaryRanges() {
11        treeMap = new TreeMap<>();
12    }
13    
14    public void addNum(int val) {
15        if(treeMap.containsKey(val)) return;
16        Integer lowerKey = treeMap.lowerKey(val);
17        Integer higherKey = treeMap.higherKey(val);
18        
19        if(lowerKey != null && treeMap.get(lowerKey)[1] + 1 >= val && higherKey != null && higherKey - 1 == val) {
20            treeMap.get(lowerKey)[1] = treeMap.get(higherKey)[1];
21            treeMap.remove(higherKey);
22        } else if(lowerKey != null && treeMap.get(lowerKey)[1] + 1 >= val) {
23            treeMap.get(lowerKey)[1] = Math.max(treeMap.get(lowerKey)[1], val);
24        } else if(higherKey != null && higherKey - 1 == val) {
25            treeMap.put(val, new int[] {val, treeMap.get(higherKey)[1]});
26            treeMap.remove(higherKey);
27        } else {
28            treeMap.put(val, new int[]{val, val});
29        }
30    }
31    
32    public int[][] getIntervals() {
33        int[][] intervals = new int[treeMap.size()][];
34        int index = 0;
35        
36        for(int[] interval : treeMap.values()) {
37            intervals[index++] = interval;
38        }
39        return intervals;
40    }
41}

JavaScript Solution

JavaScript's Map object does not have direct equivalents to the lowerKey or higherKey methods. However, that should not be a problem as we can implement these ourselves.

1
2js
3class SummaryRanges {
4    constructor() {
5        this.map = new Map();
6    }
7
8    addNum(val) {
9        if(this.map.get(val)) return;
10        let low = Array.from(this.map.entries()).reverse().find(([key, val]) => key < val);
11        let high = Array.from(this.map.entries()).find(([key, val]) => key > val);
12        
13        if (low !== undefined && this.map.get(low[1])[1] + 1 >= val && high !== undefined && high[0] - 1 === val) {
14            this.map.set(low[0], [low[0], this.map.get(high[0])[1]]);
15            this.map.delete(high[0]);
16        } else if (low !== undefined && this.map.get(low[1])[1] + 1 >= val) {
17            this.map.set(low[0], [low[0], Math.max(this.map.get(low[0])[1], val)]);
18        } else if (high !== undefined && high[0] - 1 === val) {
19            this.map.set(val, [val, this.map.get(high[0])[1]]);
20            this.map.delete(high[0]);
21        } else {
22            this.map.set(val, [val, val]);
23        }
24    }
25
26    getIntervals() {
27        return Array.from(this.map.values());
28    }
29}

C++ Solution

In C++, we will use the same logic with a combination of maps and sets for updating our intervals.

1
2cpp
3class SummaryRanges
4{
5public:
6    map<int, int> intervals;
7
8    void addNum(int val)
9    {
10        intervals[val] = val; // Add new interval [val, val]
11
12        // Merge with the previous interval if [prev_end + 1, val]
13        auto next = intervals.find(val);
14        auto prev = next; prev--;
15        if (intervals.begin() != next && prev->second + 1 >= val)
16            intervals[prev->first] = intervals[next->first],
17            intervals.erase(next), next = prev;
18
19        // Merge with the next interval if [val, next_begin - 1]
20        next++;
21        if (next != intervals.end() && next->first - 1 <= intervals[val])
22            intervals[val] = next->second,
23            intervals.erase(next);
24    }
25
26    vector<vector<int>> getIntervals()
27    {
28        vector<vector<int>> vec;
29        for (auto&a : intervals) vec.push_back({ a.first,a.second });
30        return vec;
31    }
32};

C# Solution

Similarly, in C#, we can use SortedSet data structure, which provides us with the features of the TreeMap in Java.

1
2csharp
3public class SummaryRanges {
4
5    private SortedSet<int[]> intervals;
6
7    /** Initialize your data structure here. */
8    public SummaryRanges() {
9        intervals = new SortedSet<int[]>(Comparer<int[]>.Create((a, b) => a[0] - b[0]));
10    }
11    
12    public void AddNum(int val) {
13        int[] newInterval = new int[] {val, val};
14        int[] prev = intervals.SkipWhile(i => i[1] < val - 1).FirstOrDefault();
15        int[] next = intervals.SkipWhile(i => i[0] <= val).FirstOrDefault();
16        
17        if (prev != null) {
18            intervals.Remove(prev);
19            if (prev[1] >= val)
20                val = prev[0];
21            else
22                newInterval[0] = prev[0];
23        }
24        if (next != null && next[0] <= val + 1) {
25            intervals.Remove(next);
26            newInterval[1] = next[1];
27        }
28        intervals.Add(newInterval);
29    }
30    
31    public int[][] GetIntervals() {
32        return intervals.ToArray();
33    }
34}

Overall, this problem demonstrates how using the appropriate data structure can help us in efficiently solving the problem despite it being considered difficult. The time complexity of adding a number is O(log N) - where N is the number of disjoint intervals in the stream - due to the operations with TreeMap or equivalent data structures.The space complexity is O(N), as we are storing the disjoint intervals. Consequently, the primary factor impacting performance is the number of disjoint intervals and not the size of the stream of numbers being input.