Welcome to Subscribe On Youtube

352. Data Stream as Disjoint Intervals

Description

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

 

Constraints:

  • 0 <= value <= 104
  • At most 3 * 104 calls will be made to addNum and getIntervals.
  • At most 102 calls will be made to getIntervals.

 

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Solutions

Use TreeMap

To get previous range last index, and next range first index. Then compare and decide if merge or not.

Integer l = tree.lowerKey(val);  // @note: Returns the greatest key strictly less than the given key

Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key

Interval start/end check

Every time a new number val comes in, a new interval [val, val] is generated, and an empty interval array res is created, and a variable cur is used to store the position of the new interval.

Traverse the existing interval array intervals, for each traversed current interval interval,

  • If the end position of the interval to be added plus 1 is smaller than the start position of the current interval, indicating that the two are not connected, add the current interval to res.
  • Otherwise, when the start position of the interval to be added is greater than the end position of the current position plus 1, it means that there is no intersection between the two, and the current interval can be added to res,
    • But at this time, cur should be incremented by 1 because the position to be added to the interval is behind the current interval.
  • Otherwise, the two will overlap and need to be merged,
    • At this time, use the smaller of the two starting positions to update the starting position of the interval to be added,
    • In the same way, use the larger of the two end positions to update the end position of the interval to be added.

Finally, the interval to be added is placed at the cur position in res, and then res is assigned to intervals

Solution - more python filter-lambda tricks

Class Initialization: __init__(self)

  • Initializes an empty list self.intervals which will store the intervals as lists of two elements [start, end].

Method: insert(self, newInterval: List[int])

  • Parameters: Takes a newInterval represented as a list [start, end].
  • Functionality: Inserts newInterval into the existing sorted intervals (self.intervals) while maintaining the order and merging overlapping or adjacent intervals.
  • Implementation:
    • Empty Intervals Check: If self.intervals is empty, newInterval is directly appended to it.
    • Splitting Intervals: Divides the existing intervals into two parts:
      • left: Intervals that end before newInterval starts (no overlap or adjacency).
      • right: Intervals that start after newInterval ends (no overlap or adjacency).
    • Merging: If there are intervals that overlap with or are adjacent to newInterval, it finds the minimum start (s) and maximum end (e) among those intervals and newInterval to merge them into a single interval.
    • Updating Intervals: Updates self.intervals by concatenating left, the merged interval [s, e], and right.

Method: addNum(self, val: int) -> None

  • A convenience method that wraps insert to add a single number as an interval [val, val].

Method: getIntervals(self) -> List[List[int]]

  • Simply returns the current list of intervals.

Key Points

  • Efficiency: The method insert is designed to efficiently handle the insertion and merging of intervals by using the filter function to separate intervals that don’t need merging (left and right) and directly merging the ones that overlap with or are adjacent to newInterval.
  • Maintaining Order: The intervals are kept sorted by their start times, which simplifies the process of merging and searching.
  • Simplicity in addNum: By treating the addition of a single number as adding a zero-length interval, the same insertion logic can be reused without duplication.

Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

  • lots of merges -> add() cannot be too costy
  • the number of disjoint intervals are small -> get() can be costy

to reduce cost of add(), use O(logn) for insertion of points (no merge), and maintain order get will have to calculate the disjoint intervals on the fly (basically lazy loading, do a merge on get() trigger)

  • class SummaryRanges {
    private TreeMap<Integer, int[]> mp;

    public SummaryRanges() {
        mp = new TreeMap<>();
    }

    public void addNum(int val) {
        Integer l = mp.floorKey(val);
        Integer r = mp.ceilingKey(val);
        if (l != null && r != null && mp.get(l)[1] + 1 == val && mp.get(r)[0] - 1 == val) {
            mp.get(l)[1] = mp.get(r)[1];
            mp.remove(r);
        } else if (l != null && val <= mp.get(l)[1] + 1) {
            mp.get(l)[1] = Math.max(val, mp.get(l)[1]);
        } else if (r != null && val >= mp.get(r)[0] - 1) {
            mp.get(r)[0] = Math.min(val, mp.get(r)[0]);
        } else {
            mp.put(val, new int[] {val, val});
        }
    }

    public int[][] getIntervals() {
        int[][] res = new int[mp.size()][2];
        int i = 0;
        for (int[] range : mp.values()) {
            res[i++] = range;
        }
        return res;
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * int[][] param_2 = obj.getIntervals();
 */

  • class SummaryRanges {
private:
    map<int, vector<int>> mp;

public:
    SummaryRanges() {
    }

    void addNum(int val) {
        auto r = mp.upper_bound(val);
        auto l = r == mp.begin() ? mp.end() : prev(r);
        if (l != mp.end() && r != mp.end() && l->second[1] + 1 == val && r->second[0] - 1 == val) {
            l->second[1] = r->second[1];
            mp.erase(r);
        } else if (l != mp.end() && val <= l->second[1] + 1)
            l->second[1] = max(val, l->second[1]);
        else if (r != mp.end() && val >= r->second[0] - 1)
            r->second[0] = min(val, r->second[0]);
        else
            mp[val] = {val, val};
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> res;
        for (auto& range : mp) res.push_back(range.second);
        return res;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */

  • # Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e


# better and easier, manual filter() via while
# I like this one the most
class SummaryRanges:
    def __init__(self):
        self.intervals = []

    def addNum(self, val: int) -> None:
        new_interval = [val, val]
        merged_intervals = []
        i = 0

        # before overlap part
        while i < len(self.intervals) and self.intervals[i][1] < val - 1:
            merged_intervals.append(self.intervals[i])
            i += 1

        # process overlap
        while i < len(self.intervals) and self.intervals[i][0] <= val + 1:
            new_interval[0] = min(new_interval[0], self.intervals[i][0])
            new_interval[1] = max(new_interval[1], self.intervals[i][1])
            i += 1

        merged_intervals.append(new_interval)

        # after overlap part
        while i < len(self.intervals):
            merged_intervals.append(self.intervals[i])
            i += 1

        # also passed OJ, instead of while loop:
        # merged_intervals.extend(self.intervals[i:])

        self.intervals = merged_intervals

    def getIntervals(self) -> List[List[int]]:
        return self.intervals

############

class SummaryRanges: # passed OJ, optimized below solution

  def __init__(self):
    self.intervals = []

  def insert(self, newInterval: List[int]):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """
    intervals = self.intervals
    # print intervals
    if not intervals:
      intervals.append(newInterval)
      return

    s, e = newInterval[0], newInterval[1]
    left = list(filter(lambda x: x[1] + 1 < newInterval[0], intervals))
    right = list(filter(lambda x: x[0] - 1 > newInterval[1], intervals))

    if left + right != intervals:
      s = min(intervals[len(left)][0], s)
      e = max(intervals[~len(right)][1], e)

    # +1 or -1 check: included in lambda's '+1<' and '-1>'
    self.intervals = left + [ [s, e] ] + right

  def addNum(self, val: int) -> None:
    self.insert([val, val])

  def getIntervals(self) -> List[List[int]]:

    return self.intervals


############


class SummaryRanges: # above is optimized version

  def __init__(self):
    self.intervals = []

  def insert(self, newInterval: List[int]):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """
    intervals = self.intervals
    # print intervals
    if not intervals:
      intervals.append(newInterval)
      return
    s, e = newInterval[0], newInterval[1]
    left = list(filter(lambda x: x[1] < newInterval[0], intervals))
    right = list(filter(lambda x: x[0] > newInterval[1], intervals))
    # print left, right, (s, e)
    if left + right != intervals:
      s = min(intervals[len(left)][0], s)
      e = max(intervals[~len(right)][1], e)
    newIntv = [s, e]

    # merging piece is different from above solution
    if left and left[-1][1] + 1 == s:
      newIntv[0] = left[-1][0]
      left = left[:-1]  # cut out last one, which is merged with newIntv
    if right and right[0][0] - 1 == e:
      newIntv[1] = right[0][1]
      right = right[1:]  # cut out first one, which is merged with newIntv
    self.intervals = left + [newIntv] + right

  def addNum(self, val: int) -> None:
    self.insert([val, val])

  def getIntervals(self) -> List[List[int]]:

    return self.intervals

# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()


############

'''
>>> mp = SortedDict()
>>> mp.bisect_right(3)
0


>>> mp = SortedDict()
>>> mp[1]=[1,1]
>>> mp[3]=[3,3]
>>> mp[5]=[5,5]
>>>
>>> mp
SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]})
>>> mp.bisect_right(-10)
0
>>> mp.bisect_right(100)
3
>>> mp.bisect_right(2)
1
>>> mp.values()
SortedValuesView(SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]}))
>>> list(mp.values())
[[1, 1], [3, 3], [5, 5]]
>>>
'''
from sortedcontainers import SortedDict

class SummaryRanges:
    def __init__(self):
        self.mp = SortedDict()

    def addNum(self, val: int) -> None:
        n = len(self.mp)
        ridx = self.mp.bisect_right(val)
        lidx = n if ridx == 0 else (ridx - 1) # n is similar to java treemap returning null
        keys = self.mp.keys()
        values = self.mp.values()
        if (
            lidx != n
            and ridx != n
            and values[lidx][1] + 1 == val
            and values[ridx][0] - 1 == val
        ):
            self.mp[keys[lidx]][1] = self.mp[keys[ridx]][1]
            self.mp.pop(keys[ridx])
        elif lidx != n and val <= values[lidx][1] + 1: # <= because, it could be [1 -> 10], and new add is [5,5]
            self.mp[keys[lidx]][1] = max(val, self.mp[keys[lidx]][1])
        elif ridx != n and val >= values[ridx][0] - 1:
            self.mp[keys[ridx]][0] = min(val, self.mp[keys[ridx]][0])
        else:
            self.mp[val] = [val, val]

    def getIntervals(self) -> List[List[int]]:
        return list(self.mp.values())


# # Your SummaryRanges object will be instantiated and called as such:
# # obj = SummaryRanges()
# # obj.addNum(val)
# # param_2 = obj.getIntervals()

All Problems

All Solutions