Python solution


  • 0
    G
    class KeyNode():
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None
    
    class ValueBucket():
        def __init__(self, val):
            self.val = val
            self.prev = None
            self.next = None
            self.keyHead = KeyNode(None, val)
            self.keyTail = KeyNode(None, val)
            
            self.keyHead.next = self.keyTail
            self.keyTail.prev = self.keyHead
    
    class AllOne(object):
    
        def __init__(self):
            
            self.valueBuckets = {}
            self.headBucket = ValueBucket(None)
            self.tailBucket = ValueBucket(None)
            
            self.headBucket.next = self.tailBucket
            self.tailBucket.prev = self.headBucket
            
            self.keys = {}
    
        def inc(self, key):
    
            if key not in self.keys:
                keyNode = self.keys[key] = KeyNode(key, 1)
                
                if 1 not in self.valueBuckets:
                    # create new bucket of value 1
                    bucket = self.valueBuckets[1] = ValueBucket(1)
                    prev = self.tailBucket.prev
                    prev.next = bucket
                    bucket.prev = prev
                    bucket.next = self.tailBucket
                    self.tailBucket.prev = bucket
                
                keyTail = self.valueBuckets[1].keyTail
                
                # attache the new key to the value 1 bucket
                prev = keyTail.prev
                prev.next = keyNode
                keyNode.prev = prev
                keyNode.next = keyTail
                keyTail.prev = keyNode
            else:
                keyNode = self.keys[key]
                oldBucket = self.valueBuckets[keyNode.val]
                oldVal = keyNode.val
                newVal = keyNode.val + 1
                keyNode.val += 1
                
                # remove from the old bucket
                prev = keyNode.prev
                prev.next = keyNode.next
                keyNode.next.prev = prev
                
                newBucket = None
                if newVal in self.valueBuckets:
                    newBucket = self.valueBuckets[newVal]
                else:
                    newBucket = self.valueBuckets[newVal] = ValueBucket(newVal)
                    
                    # insert the new bucket
                    prev = oldBucket.prev
                    prev.next = newBucket
                    oldBucket.prev = newBucket
                    newBucket.prev = prev
                    newBucket.next = oldBucket
                
                # attach to the new bucket
                prev = newBucket.keyTail.prev
                prev.next = keyNode
                newBucket.keyTail.prev = keyNode
                keyNode.prev = prev
                keyNode.next = newBucket.keyTail
                
                if oldBucket.keyHead.next is oldBucket.keyTail:
                    prev = oldBucket.prev
                    prev.next = oldBucket.next
                    oldBucket.next.prev = prev
                    del self.valueBuckets[oldVal]
                    
            
    
        def dec(self, key):
    
            if key in self.keys:
                keyNode = self.keys[key]
                oldVal = keyNode.val
                oldBucket = self.valueBuckets[keyNode.val]
                keyNode.val -= 1
                
                # detach from old bucket's linked list
                prev = keyNode.prev
                prev.next = keyNode.next
                keyNode.next.prev = prev
                
                # remove it from the data structure
                if keyNode.val == 0:
                    
                    del self.keys[key]
                
                # decrement it by 1
                else:
                    keyTail = None
                    
                    if keyNode.val in self.valueBuckets:
                        keyTail = self.valueBuckets[keyNode.val].keyTail
    
                    else:
                        bucket = self.valueBuckets[keyNode.val] = ValueBucket(keyNode.val)
                        
                        next = oldBucket.next
                        oldBucket.next = bucket
                        next.prev = bucket
                        bucket.prev = oldBucket
                        bucket.next = next
                        
                        keyTail = bucket.keyTail
                    
                    prev = keyTail.prev
                    prev.next = keyNode
                    keyTail.prev = keyNode
                    keyNode.prev = prev
                    keyNode.next = keyTail
                
                # if bucket is empty
                if oldBucket.keyHead.next is oldBucket.keyTail:
                    prev = oldBucket.prev
                    prev.next = oldBucket.next
                    oldBucket.next.prev = prev
                
                    del self.valueBuckets[oldVal]
    
        
    
        def getMaxKey(self):
            
            if self.headBucket.next is not self.tailBucket:
                return self.headBucket.next.keyHead.next.key
            else:
                return ''
            
    
        def getMinKey(self):
    
            if self.headBucket.next is not self.tailBucket:
                return self.tailBucket.prev.keyHead.next.key
            else:
                return ''
    
    

    Just a two-layer doubly linked list + hashtable solution


Log in to reply
 

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