BinarySearch 0795 Number Stream to Intervals

Problem statement

https://binarysearch.com/problems/Number-Stream-to-Intervals/

Solution

Equal to Leetcode 0352. Data Stream as Disjoint Intervals.

Complexity

Time complexity is O(1) for add and O(k log k) <= O(n log n) for get. Space complexity is potentially O(n).

Code

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

    def add(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 get(self):
        return sorted([[i, self.d1[i]] for i in self.d1])