{x}
blog image

All O`one Data Structure

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.

Solution Explanation for LeetCode 432: All O(1) Data Structure

This problem requires designing a data structure that efficiently handles string counts, allowing for incrementing, decrementing, and retrieving keys with minimum and maximum counts, all within O(1) average time complexity. A simple hash table won't suffice because finding min/max requires O(n) traversal. The optimal solution uses a combination of a hash table and a doubly linked list.

Data Structure:

  1. Hash Table (nodes): Maps each string key to its corresponding node in the doubly linked list. This allows O(1) access to a string's node.

  2. Doubly Linked List: Nodes in this list are sorted by count. Each node contains:

    • cnt: The count of strings with this value.
    • keys: A set of strings with the same count.
    • prev, next: Pointers to the previous and next nodes in the list.

    A dummy root node simplifies the handling of edge cases (empty list).

Algorithm:

  1. __init__(self): Initializes the root node and the nodes hash table.

  2. inc(self, key):

    • If key is not in nodes, create a new node with count 1 and insert it into the appropriate place in the doubly linked list (maintaining sorted order by count).
    • If key exists, find its node. Increment its count. If a node with the new count doesn't exist, create one and insert it. Otherwise, move the key to the existing node. Remove the old node if it becomes empty after the key is moved.

  3. dec(self, key):

    • Find the node for key. Decrement its count.
    • If the count becomes 0, remove the key from the node and the key from nodes.
    • If the count is greater than 0, create a new node with the decremented count and insert it if necessary; otherwise move the key to the existing node. Remove the old node if empty.

  4. getMaxKey(self): Returns an arbitrary key from the node before the root. This node contains the keys with the highest count.

  5. getMinKey(self): Returns an arbitrary key from the node after the root. This node contains the keys with the lowest count.

Time Complexity Analysis:

  • inc(key) and dec(key): O(1) on average. Hash table lookups are O(1) on average. Insertion and deletion in the doubly linked list are O(1) if we know the position to insert. In the worst case(consecutive counts), it's O(n) where n is the number of unique counts, but this is infrequent given the problem constraints. The average case is still considered O(1) due to the infrequent nature of the worst-case scenario.

  • getMaxKey() and getMinKey(): O(1). Direct access to the head and tail of the list.

Space Complexity: O(N), where N is the number of unique keys stored.

Code (Python and Java): Provided in the solution section above. Both implementations follow the algorithm and data structures described. The Python code is slightly more concise, but the Java code is equally efficient. Both are well-commented to aid in understanding.