432. All O`one Data Structure

[mah-shamim]

Topics: Hash Table, Linked List, Design, Doubly-Linked List

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

• AllOne() Initializes the object of the data structure.
• inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
• dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
• getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
• getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

Example 1:

• Input:
  ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
  [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
• Output: [null, null, null, "hello", "hello", null, "hello", "leet"]
• Explanation:
  AllOne allOne = new AllOne();
  allOne.inc("hello");
  allOne.inc("hello");
  allOne.getMaxKey(); // return "hello"
  allOne.getMinKey(); // return "hello"
  allOne.inc("leet");
  allOne.getMaxKey(); // return "hello"
  allOne.getMinKey(); // return "leet"

Constraints:

• 1 <= key.length <= 10
• key consists of lowercase English letters.
• It is guaranteed that for each call to dec, key is existing in the data structure.
• At most 5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

[kovatz]

We need to implement a data structure that allows incrementing, decrementing, and retrieving keys with the minimum and maximum counts in constant time (O(1)).

Key Insights:

1. Hash Table (for String Count):
   We need a hash table (counts) that maps each string (key) to its count. This allows for O(1) access when incrementing or decrementing the count.

2. Doubly Linked List (for Counts):
   To keep track of the minimum and maximum counts, we can use a doubly linked list where each node represents a unique count. The node will store all strings with that count in a set. The linked list will help in retrieving the min and max counts in constant time by keeping track of the head (min) and tail (max) nodes.

3. Two Hash Maps:

   • A hash map (key_to_node) will map each string (key) to the node in the doubly linked list that stores its count. This allows us to move the key from one count node to another in O(1) time when we increment or decrement the count.
   • Another hash map (counts) will map each count to its corresponding node in the doubly linked list, ensuring we can locate the node for any count in O(1) time.

Plan:

• inc(key):

  • If the key exists, increase its count by 1 and move it to the next node (create a new node if necessary).
  • If the key does not exist, create a new node with count 1 and insert it.

• dec(key):

  • Decrease the count of the key by 1.
  • If the count becomes zero, remove the key from the data structure.

• getMaxKey() and getMinKey():

  • Return the first key from the tail node (max count) or head node (min count) in constant time.

Let's implement this solution in PHP: 432. All O`one Data Structure

<?php
class AllOne {
    /**
     * @var array
     */
    private $key_to_node;
    /**
     * @var array
     */
    private $counts;
    /**
     * @var Node
     */
    private $head;
    /**
     * @var Node
     */
    private $tail;

    /**
     */
    function __construct() {
        $this->key_to_node = [];
        $this->counts = [];
        $this->head = new Node(null); // Dummy head
        $this->tail = new Node(null); // Dummy tail
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    /**
     * Insert a new node after a given node
     *
     * @param $newNode
     * @param $prevNode
     * @return void
     */
    private function insertAfter($newNode, $prevNode) {
        $newNode->next = $prevNode->next;
        $newNode->prev = $prevNode;
        $prevNode->next->prev = $newNode;
        $prevNode->next = $newNode;
    }

    /**
     * Remove a node from the linked list
     *
     * @param $node
     * @return void
     */
    private function removeNode($node) {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
        unset($this->counts[$node->count]);
    }

    /**
     * Increments the count of a key
     *
     * @param String $key
     * @return NULL
     */
    function inc($key) {
        if (!isset($this->key_to_node[$key])) {
            // Key does not exist, insert with count 1
            if (!isset($this->counts[1])) {
                $newNode = new Node(1);
                $this->insertAfter($newNode, $this->head);
                $this->counts[1] = $newNode;
            }
            $this->counts[1]->keys[$key] = true;
            $this->key_to_node[$key] = $this->counts[1];
        } else {
            // Key exists, increment its count
            $curNode = $this->key_to_node[$key];
            $curCount = $curNode->count;
            $newCount = $curCount + 1;

            // Move the key to the next count node
            unset($curNode->keys[$key]);
            if (!isset($this->counts[$newCount])) {
                $newNode = new Node($newCount);
                $this->insertAfter($newNode, $curNode);
                $this->counts[$newCount] = $newNode;
            }
            $this->counts[$newCount]->keys[$key] = true;
            $this->key_to_node[$key] = $this->counts[$newCount];

            // Remove the old node if empty
            if (empty($curNode->keys)) {
                $this->removeNode($curNode);
            }
        }
    }

    /**
     * Decrements the count of a key
     *
     * @param String $key
     * @return NULL
     */
    function dec($key) {
        if (!isset($this->key_to_node[$key])) return;

        $curNode = $this->key_to_node[$key];
        $curCount = $curNode->count;
        $newCount = $curCount - 1;

        // Remove the key from the current node
        unset($curNode->keys[$key]);

        // If the new count is 0, completely remove the key
        if ($newCount == 0) {
            unset($this->key_to_node[$key]);
        } else {
            // Move the key to the previous count node
            if (!isset($this->counts[$newCount])) {
                $newNode = new Node($newCount);
                $this->insertAfter($newNode, $curNode->prev);
                $this->counts[$newCount] = $newNode;
            }
            $this->counts[$newCount]->keys[$key] = true;
            $this->key_to_node[$key] = $this->counts[$newCount];
        }

        // Remove the old node if empty
        if (empty($curNode->keys)) {
            $this->removeNode($curNode);
        }
    }

    /**
     * Returns one of the keys with the maximum count
     *
     * @return String
     */
    function getMaxKey() {
        if ($this->tail->prev === $this->head) return "";
        return key($this->tail->prev->keys);
    }

    /**
     * Returns one of the keys with the minimum count
     *
     * @return String
     */
    function getMinKey() {
        if ($this->head->next === $this->tail) return "";
        return key($this->head->next->keys);
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * $obj = AllOne();
 * $obj->inc($key);
 * $obj->dec($key);
 * $ret_3 = $obj->getMaxKey();
 * $ret_4 = $obj->getMinKey();
 */
 
// Example usage
$allOne = new AllOne();
$allOne->inc("hello");
$allOne->inc("hello");
echo $allOne->getMaxKey(); // returns "hello"
echo $allOne->getMinKey(); // returns "hello"
$allOne->inc("leet");
echo $allOne->getMaxKey(); // returns "hello"
echo $allOne->getMinKey(); // returns "leet"
?>

Explanation:

1. Data Structure:

   • key_to_node: Maps each key to the corresponding node in the doubly linked list.
   • counts: Maps each count to its corresponding node in the doubly linked list.
   • head and tail: Dummy head and tail nodes for easier manipulation of the doubly linked list.

2. Methods:

   • inc($key): If the key exists, it increments its count and moves it to the appropriate node in the list. If not, it inserts it with count 1.
   • dec($key): Decreases the key’s count and either removes it or moves it to the appropriate node.
   • getMaxKey(): Returns the key from the node at the tail of the doubly linked list (max count).
   • getMinKey(): Returns the key from the node at the head of the doubly linked list (min count).

Complexity:

• All operations are designed to run in O(1) average time complexity.

Let me know if you need further clarifications!

[mah-shamim]

Thanks to solve this problem efficiently

[kovatz]

Thanks