Share my solution using two map


  • 1
    M

    Trying to record intervals by left and right points. Complexity of 'addNum' is log(k), complexity of 'getIntervals' is klog(k), k is number of intervals.

    ### 352. Data Stream as Disjoint Intervals ###
    class SummaryRanges(object):
    
        # Initialize your data structure here.
        def __init__(self):
            self.have, self.left, self.right = set(), {}, {}
    
        # @param {integer} val
        # @return {void}
        def addNum(self, val):
            if val in self.have: return
    
            self.have.add(val)
            if val-1 in self.right and val+1 in self.left:
                l, r = self.right.pop(val-1), self.left.pop(val+1)
                self.left.pop(l.start)
                self.right.pop(r.end)
                interval = Interval(l.start, r.end)
                self.left[l.start], self.right[r.end] = interval, interval
            elif val-1 in self.right:
                l = self.right.pop(val-1)
                self.left.pop(l.start)
                interval = Interval(l.start, val)
                self.left[l.start], self.right[val] = interval, interval
            elif val+1 in self.left:
                r = self.left.pop(val+1)
                self.right.pop(r.end)
                interval = Interval(val, r.end)
                self.left[val], self.right[r.end] = interval, interval
            else:
                interval = Interval(val, val)
                self.left[val], self.right[val] = interval, interval
    
        # @return {Interval[]}
        def getIntervals(self):
            return [self.left[key] for key in sorted(self.left.keys())]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.