LeetCode: All O`one Data Structure

Posted on January 31, 2018July 26, 2020 by braindenny

All O`one Data Structure

Similar Problems:

Implement a data structure supporting the following operations:

Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string “”.
GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string “”.

Challenge: Perform all these in O(1) time complexity.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/all-oone-data-structure
## Basic Ideas:
##          hasmap: save key and values
##          How to achieve GetMinKey() with O(1)?
##          double linked list
##
## Complexity: Time O(1), Space O(n)

class DLinkNode:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

class AllOne(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.m = {}
        # head <--> p1 <--> p2 <--> tail
        # head and tail are dummy nodes. And m[p1] <= m[p2]
        self.head = DLinkNode(None)
        self.tail = DLinkNode(None)
        self.head.right = self.tail
        self.tail.left = self.head

    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: void
        """
        if key not in self.m:
            p = DLinkNode(key)
            self.m[key] = [1, p]
            # add to head
            p.right = self.head.right
            p.right.left = p
            p.left = self.head
            self.head.right = p
        else:
            [value, p] = self.m[key]
            self.m[key] = [value+1, p]
            # keep moving to right
            while p.right != self.tail and self.m[p.key][0]>self.m[p.right.key][0]:
                # .. <--> p <--> q <--> ..
                # swap p and q
                q = p.right
                p.right = q.right
                q.left = p.left
                p.right.left = p
                q.left.right = q
                q.right = p
                p.left = q

    def dec(self, key):
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        :type key: str
        :rtype: void
        """
        if key not in self.m:
            return
        [value, p] = self.m[key]
        if value == 1:
            del self.m[key]
            # remove p, but it may not be the head
            p.left.right = p.right
            p.right.left = p.left
        else:
            self.m[key] = [value-1, p]
            # keep moving to left
            while p.left != self.head and self.m[p.key][0] < self.m[p.left.key][0]:
                # .. <--> q <--> p <--> ..
                q = p.left
                p.left = q.left
                q.right = p.right
                p.left.right = p
                q.right.left = q
                p.right = q
                q.left = p

    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        if self.head.right == self.tail:
            return ""
        else:
            return self.tail.left.key

    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        if self.head.right == self.tail:
            return ""
        else:
            return self.head.right.key

# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()

Post Views: 3