Data Stream as Disjoint Intervals LeetCode Solution

Last updated on October 9th, 2024 at 06:11 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

Topics

Binary Search, Ordered Map

Level of Question

Hard

Data Stream as Disjoint Intervals 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
Scroll to Top