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
class SummaryRanges {
 public:
  void addNum(int val) {
    if (map.count(val))
      return;

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

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

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

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

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

  // minimum in map > key
  int higherKey(int key) {
    const auto it = map.upper_bound(key);  // minimum in map > key
    if (it == cend(map))
      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
class SummaryRanges {
  public void addNum(int val) {
    if (map.containsKey(val))
      return;

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

    // {lo, map.get(lo)[1]} + val + {hi, map.get(hi)[1]} = {lo, map.get(hi)[1]}
    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);
      // {lo, map.get(lo)[1]} + val = {lo, val}
      // (prevent adding duplicate entry by using '>=' instead of '==')
    } else if (lo != null && map.get(lo)[1] + 1 >= val) {
      map.get(lo)[1] = Math.max(map.get(lo)[1], val);
      // val + {hi, map.get(hi)[1]} = {val, map.get(hi)[1]}
    } 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<>();
}