Data Stream as Disjoint Intervals LeetCode Solution

Last updated on January 29th, 2025 at 02:12 am

Here, we see a Data Stream as Disjoint Intervals LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search, Ordered Map

Level of Question

Hard

Data Stream as Disjoint Intervals LeetCode Solution

Data Stream as Disjoint Intervals LeetCode Solution

1. Problem Statement

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 integer value to 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 by starti.

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]]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Merge Intervals”. This pattern is used to manage and merge overlapping or adjacent intervals efficiently. The goal is to maintain a collection of disjoint intervals and update them dynamically as new numbers are added.

3. Code Implementation in Different Languages

3.1 Data Stream as Disjoint Intervals C++

class SummaryRanges {
public:
    SummaryRanges() {
        
    }
    
    void addNum(int value) {
        auto it = _map.lower_bound(value);
        bool merged = false;
        if(it != _map.begin()) {
            auto prev = it;
            --prev;
            if(prev->second + 1 >= value) {
                merged = true;
                prev->second = max(prev->second, value);
            }
        }

        if(it != _map.end()) {
            if(it->first - 1 <= value) {
                if(merged) {
                    auto prev = it;
                    --prev;
                    if(prev->second >= it->first - 1) {
                        prev->second = max(prev->second, it->second);
                        _map.erase(it);
                    }
                } else {
                    merged = true;
                    if(it->first != value) {
                        pair<int, int> p = *it;
                        p.first = min(p.first, value);
                        it = _map.insert(it, p);
                        ++it;
                        if(it != _map.end())
                            _map.erase(it);
                    }
                }
            }
        }
        if(!merged)
            _map.insert(it, {value, value});
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> intervals;
        for(auto const & p : _map)
            intervals.push_back({p.first, p.second});
        return intervals;
    }

    map<int, int> _map;
};

3.2 Data Stream as Disjoint Intervals Java

class SummaryRanges {
  public SummaryRanges() {
        
    }
  public void addNum(int val) {
    if (map.containsKey(val))
      return;

    final Integer lo = map.lowerKey(val);
    final Integer hi = map.higherKey(val);

    if (lo != null && hi != null && map.get(lo)[1] + 1 == val && val + 1 == hi) {
      map.get(lo)[1] = map.get(hi)[1];
      map.remove(hi);
    } else if (lo != null && map.get(lo)[1] + 1 >= val) {
      map.get(lo)[1] = Math.max(map.get(lo)[1], val);
    } else if (hi != null && val + 1 == hi) {
      map.put(val, new int[] {val, map.get(hi)[1]});
      map.remove(hi);
    } else {
      map.put(val, new int[] {val, val});
    }
  }

  public int[][] getIntervals() {
    List<int[]> intervals = new ArrayList<>(map.values());
    return intervals.toArray(new int[intervals.size()][]);
  }

  // {start: {start, end}}
  private TreeMap<Integer, int[]> map = new TreeMap<>();
}

3.3 Data Stream as Disjoint Intervals JavaScript

var SummaryRanges = function() {
    this.arr = []
};

SummaryRanges.prototype.addNum = function(val) {
    let valIsInside = false;
    for(let i =0; i<this.arr.length;i++){
        let [x,y] = this.arr[i];
        if(val >=x && val<=y){
            valIsInside = true;
            break;
        }
        else if(val === y + 1){
            this.arr[i][1] = val;
            if(val + 1 === this.arr[i+1]?.[0]){
                this.arr[i][1] = this.arr[i+1][1]
                this.arr.splice(i+1,1)
            }
            valIsInside = true;
            break;
        }
        else if(val < x){
            if(val + 1 == x){
                this.arr[i][0] = val;
            }
            else this.arr.splice(i,0,[val,val])
            valIsInside = true;
            break;
        }
    }
    if(!valIsInside) this.arr.push([val,val])
};

SummaryRanges.prototype.getIntervals = function() {
    return this.arr
};

3.4 Data Stream as Disjoint Intervals Python

class SummaryRanges:
    def __init__(self):
        self.nums = set()
        
    def addNum(self, value):
        self.nums.add(value)
        
    def getIntervals(self):
        intervals = []
        start = None
        end = None
        for val in self.nums:
            if start is None:
                start = val
                end = val
            elif val - end == 1:
                end = val
            else:
                intervals.append([start, end])
                start = end = val
        if start is not None:
            intervals.append([start, end])
        return intervals

4. Time and Space Complexity

Space Complexity
C++O(n)
JavaO(n)
JavaScriptO(n)
PythonO(n)
  • The C++ and Java implementations are the most efficient for addNum due to the use of balanced binary search trees (map and TreeMap).
  • The Python implementation is the least efficient for getIntervals due to the need to sort the set of numbers.
  • The JavaScript implementation is less efficient for addNum due to the linear search in the array.
Scroll to Top