Data Stream as Disjoint Intervals LeetCode solution in Java

1
class SummaryRanges {
2

3
  Map<Integer, int[]> st;
4
  Map<Integer, int[]> end;
5
  Set<Integer> pending;
6
  int[][] prev = new int[0][];
7
  Set<Integer> seen = new HashSet<>();
8
  int INVALID = -1;
9

10
  public SummaryRanges() {
11
    st = new HashMap<>();
12
    end = new HashMap<>();
13
    pending = new HashSet<>();
14
  }
15

16
  public void addNum(int val) { // [TC: O(1)]
17
    if (!seen.contains(val)) { // only add if not seen.
18
      pending.add(val); // pending processing list
19
    }
20
  }
21

22
  public int[][]
23
      getIntervals() { // [TC: O(pending list length (= k)) best case (all merges), O(n)+O(klogk)
24
    // worst case (all inserts)]
25
    Set<int[]> addSet = new HashSet<>();
26
    for (int n : pending) {
27
      if (st.containsKey(n + 1)
28
          && end.containsKey(
29
              n - 1)) { // merge intervals on both ends, a new interval form -> add to addSet
30
        int[] s = st.get(n + 1);
31
        int[] e = end.get(n - 1);
32
        int[] m = new int[] {e[0], s[1]};
33
        st.remove(n + 1);
34
        end.remove(n - 1);
35
        st.put(m[0], m);
36
        end.put(m[1], m);
37
        s[0] = e[0] = INVALID;
38
        addSet.remove(s); // may be in addSet, remove them
39
        addSet.remove(e);
40
        addSet.add(m);
41
      } else if (st.containsKey(n + 1)) { // merge with the next interval, no other action required.
42
        st.get(n + 1)[0]--;
43
        st.put(n, st.get(n + 1));
44
        st.remove(n + 1);
45
      } else if (end.containsKey(
46
          n - 1)) { // merge with the previous interval, no other action required.
47
        end.get(n - 1)[1]++;
48
        end.put(n, end.get(n - 1));
49
        end.remove(n - 1);
50
      } else { // new interval -> add to AddSet
51
        int[] m = new int[] {n, n};
52
        addSet.add(m);
53
        st.put(n, m);
54
        end.put(n, m);
55
      }
56
    }
57

58
    seen.addAll(pending);
59
    pending.clear(); // remember to clear the pending list.
60

61
    if (!addSet.isEmpty()) { // IF there is no new intervals to insert, we SKIP this.
62
      List<int[]> addList = new ArrayList<>(addSet);
63
      addList.sort(Comparator.comparingInt(o -> o[0]));
64
      int i = 0, j = 0; // two pointers because both prev & addList are sorted.
65
      List<int[]> ans = new ArrayList<>();
66
      while (i < prev.length || j < addList.size()) {
67
        if (i < prev.length && prev[i][0] == INVALID) {
68
          i++;
69
        } else if (j == addList.size() || i < prev.length && prev[i][0] < addList.get(j)[0]) {
70
          ans.add(prev[i++]);
71
        } else if (i == prev.length || prev[i][0] > addList.get(j)[0]) {
72
          ans.add(addList.get(j++));
73
        }
74
      }
75
      prev = ans.toArray(new int[0][]);
76
    }
77

78
    return prev;
79
  }
80
}