Python solution using dict addNum O(1) and getInterval O(n)


  • 0
    M
    class SummaryRanges(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.start_hash={};
            self.end_hash={};
            self.stream={};
    
        def addNum(self, val):
            """
            :type val: int
            :rtype: void
            """
            if val not in self.stream:
                self.stream[val]=1;
            else:
                return;
            
            if val-1 not in self.end_hash and val+1 not in self.start_hash:
                self.start_hash[val]=val;
                self.end_hash[val]=val;
            elif val-1 not in self.end_hash:
                end=self.start_hash[val+1];
                self.start_hash.pop(val+1);
                self.end_hash.pop(end);
                self.start_hash[val]=end;
                self.end_hash[end]=val;
            elif val+1 not in self.start_hash:
                start=self.end_hash[val-1];
                self.end_hash.pop(val-1);
                self.start_hash.pop(start);
                self.start_hash[start]=val;
                self.end_hash[val]=start;
            else:
                start=self.end_hash[val-1];
                end=self.start_hash[val+1];
                
                self.start_hash.pop(val+1);
                self.end_hash.pop(end);
                
                self.start_hash.pop(start);
                self.end_hash.pop(val-1);
                
                self.start_hash[start]=end;
                self.end_hash[end]=start;
            
        def getIntervals(self):
            """
            :rtype: List[Interval]
            """
            rt=[];
            for k in sorted(self.start_hash.keys()):
                rt.append(Interval(k,self.start_hash[k]));
            
            return rt;
    

Log in to reply
 

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