Last updated on October 25th, 2024 at 10:25 pm

Here, We see Data Stream as Disjoint Intervals LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Data Stream as Disjoint Intervals LeetCode Solution

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

1. Data Stream as Disjoint Intervals LeetCode Solution 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;
};

2. Data Stream as Disjoint Intervals LeetCode Solution 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. Data Stream as Disjoint Intervals LeetCode Solution 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
};

4. Data Stream as Disjoint Intervals LeetCode Solution 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