Skip to content

352. Data Stream as Disjoint Intervals 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class SummaryRanges {
 public:
  void addNum(int val) {
    if (intervals.count(val))
      return;

    const int lo = lowerKey(val);
    const int hi = higherKey(val);

    // {lo, intervals[lo][1]} + val + {hi, intervals[hi][1]} = {lo,
    // intervals[hi][1]}
    if (lo >= 0 && hi >= 0 && intervals[lo][1] + 1 == val && val + 1 == hi) {
      intervals[lo][1] = intervals[hi][1];
      intervals.erase(hi);
      // {lo, intervals[lo][1]} + val = {lo, val}
      // Prevent adding duplicate entry by using '>=' instead of '=='.
    } else if (lo >= 0 && intervals[lo][1] + 1 >= val) {
      intervals[lo][1] = max(intervals[lo][1], val);
    } else if (hi >= 0 && val + 1 == hi) {
      // val + {hi, intervals[hi][1]} = {val, intervals[hi][1]}
      intervals[val] = {val, intervals[hi][1]};
      intervals.erase(hi);
    } else {
      intervals[val] = {val, val};
    }
  }

  vector<vector<int>> getIntervals() {
    vector<vector<int>> res;
    for (const auto& [_, interval] : intervals)
      res.push_back(interval);
    return res;
  }

 private:
  map<int, vector<int>> intervals;  // {start: (start, end)}

  // Returns the maximum key in `intervals` < `key`.
  int lowerKey(int key) {
    auto it = intervals.lower_bound(key);
    if (it == intervals.begin())
      return -1;
    return (--it)->first;
  }

  // Returns the minimum key in `intervals` > `key`.
  int higherKey(int key) {
    const auto it = intervals.upper_bound(key);
    if (it == intervals.cend())
      return -1;
    return it->first;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class SummaryRanges {
  public void addNum(int val) {
    if (intervals.containsKey(val))
      return;

    // the maximum key in `intervals` < `key`
    final Integer lo = intervals.lowerKey(val);
    // the minimum key in `intervals` > `key`
    final Integer hi = intervals.higherKey(val);

    // {lo, intervals.get(lo)[1]} + val + {hi, intervals.get(hi)[1]} = {lo, intervals.get(hi)[1]}
    if (lo != null && hi != null && intervals.get(lo)[1] + 1 == val && val + 1 == hi) {
      intervals.get(lo)[1] = intervals.get(hi)[1];
      intervals.remove(hi);
      // {lo, intervals.get(lo)[1]} + val = {lo, val}
      // Prevent adding duplicate entry by using '>=' instead of '=='.
    } else if (lo != null && intervals.get(lo)[1] + 1 >= val) {
      intervals.get(lo)[1] = Math.max(intervals.get(lo)[1], val);
      // val + {hi, intervals.get(hi)[1]} = {val, intervals.get(hi)[1]}
    } else if (hi != null && val + 1 == hi) {
      intervals.put(val, new int[] {val, intervals.get(hi)[1]});
      intervals.remove(hi);
    } else {
      intervals.put(val, new int[] {val, val});
    }
  }

  public int[][] getIntervals() {
    return intervals.values().stream().toArray(int[][] ::new);
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from sortedcontainers import SortedDict


class SummaryRanges:
  def __init__(self):
    self.intervals = SortedDict()  # {start: (start, end)}

  def addNum(self, val: int) -> None:
    if val in self.intervals:
      return

    lo = self._lowerKey(val)
    hi = self._higherKey(val)

    # {lo, map[lo][1]} + val + {hi, map[hi][1]} = {lo, map[hi][1]}
    if lo >= 0 and hi >= 0 and self.intervals[lo][1] + 1 == val and val + 1 == hi:
      self.intervals[lo][1] = self.intervals[hi][1]
      del self.intervals[hi]
      # {lo, map[lo][1]} + val = {lo, val}
      # Prevent adding duplicate entry by using '>=' instead of '=='.
    elif lo >= 0 and self.intervals[lo][1] + 1 >= val:
      self.intervals[lo][1] = max(self.intervals[lo][1], val)
    elif hi >= 0 and val + 1 == hi:
      # val + {hi, map[hi][1]} = {val, map[hi][1]}
      self.intervals[val] = [val, self.intervals[hi][1]]
      del self.intervals[hi]
    else:
      self.intervals[val] = [val, val]

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

  def _lowerKey(self, key: int):
    """Returns the maximum key in `self.intervals` < `key`."""
    i = self.intervals.bisect_left(key)
    if i == 0:
      return -1
    return self.intervals.peekitem(i - 1)[0]

  def _higherKey(self, key: int):
    """Returns the minimum key in `self.intervals` < `key`."""
    i = self.intervals.bisect_right(key)
    if i == len(self.intervals):
      return -1
    return self.intervals.peekitem(i)[0]