Problem statement

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Solution

We can keep two hash table for intervals [x1,y1], ... [xk, yk] as {x1:y1, ..., xk:yk} and {y1:x1, ... , yk:xk} as well as visited numbers. Then we can add new number v in O(1): we look for v - 1 and v + 1 in our tables. We need to consider 4 different cases:

  1. When we have [x...v-1] [v+1 ... y], then we need to merge two intervals to one.
  2. When we have [x...v-1], then we need to extend this interval.
  3. When we have [v+1...y], then we need to extend this interval.
  4. When we have [], then we need to create new interval [v].

To implement getIntervals, we need to sort intervals and return the answer.

Complexity

Time complexity is O(1) for addNum and O(k log k) <= O(n log n) for getIntervals. Space complexity is potentiallly O(n).

Code

class SummaryRanges:
    def __init__(self):
        self.d1, self.d2, self.all = {}, {}, set()

    def addNum(self, v):
        if v in self.all: return
        self.all.add(v)
        i1 = self.d2.get(v - 1, -1)
        i2 = self.d1.get(v + 1, -1)
        lft, rgh = v - 1 in self.d2, v + 1 in self.d1
                
        if lft and rgh:
            self.d1[i1] = i2
            self.d2[i2] = i1
        elif lft and not rgh:
            self.d1[i1] = v
            self.d2[v] = i1
        elif not lft and rgh:
            self.d2[i2] = v
            self.d1[v] = i2
        else:
            self.d1[v] = v
            self.d2[v] = v
            
        self.d2.pop(v - 1, None)
        self.d1.pop(v + 1, None)

    def getIntervals(self):
        return sorted([[i, self.d1[i]] for i in self.d1])