432. All O`one Data Structure

HardDesignHash TableLinked ListDoubly-Linked List
Leetcode Link

Problem Description

The LeetCode problem requires the design of a special data structure that supports the following operations on strings and their associated counts:

  • Incrementing the count of a given string.
  • Decrementing the count of a given string.
  • Retrieving a string with the maximum count.
  • Retrieving a string with the minimum count.

An important constraint is that each of these operations should be completed in constant time, O(1), on average.

Intuition

To solve this problem, we aim to maintain a doubly-linked list where each node represents a unique count and stores the keys (strings) with that count. The nodes of the list are kept in sorted order, that is, in increasing order of the counts.

Here's the underlying intuition behind the data structure and its operations:

  • Using a Doubly Linked List: This allows easy insertion and deletion of nodes which represent counts of keys. A node can quickly connect to its neighbors without having to shift elements, as would be necessary in an array.

  • Maintaining a root Node: The root node acts as a sentinel that enables the list to be circular, which simplifies the edge cases for insertions and deletions at the beginning and end of the list.

  • Storing Keys in Sets within Nodes: Each node contains a set of keys with the corresponding count for that node. Using a set ensures that we handle the keys efficiently when incrementing and decrementing their counts.

  • Hashtable to Store References to Nodes: A hashtable (nodes dictionary in Python code) keeps track of the nodes associated with each key. This enables constant-time access to the nodes when incrementing or decrementing counts.

Operations Explained:

  • Increment (inc): When a key's count is incremented:

    • If the key is new, it is either added to a new node with count 1 or to an existing node if it directly follows the root node with a count of 1.

    • If the key already exists in a node, we either create a new node with an incremented count right after the current node (if the incremented count does not match the next node's count) or we add the key to the set of the next node.

  • Decrement (dec): When a key's count is decremented:

    • If the count comes down to 0, the key is removed from the hashtable.

    • If the key's count after decrementing doesn't match the previous node's count (or no previous node exists), a new node is created with the decremented count. Otherwise, the key is added to the previous node's set.

  • Get Maximum (getMaxKey) and Get Minimum (getMinKey): To retrieve the keys with maximum and minimum counts, we can directly access the sets in the last and first nodes, respectively, from the root due to the order maintained in the doubly-linked list.

By carefully maintaining the structure of the linked list and the hashtable, we can achieve the required constant average time complexity for each operation mandated by the problem.

Learn more about Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

Solution Approach

The implementation of the solution involves the following data structures and algorithms:

  • A Doubly Linked List is used to maintain the counts of strings in ascending order, enabling O(1) insertion and deletion at both ends and in between nodes.
  • A Hashtable or dictionary in Python (nodes in the given code) is used to keep track of which node is associated with which key to ensure O(1) access time.
  • Each node also includes a Set to store all keys having the same count, allowing for O(1) addition and deletion of keys within a node.

Node Class

The Node class represents each node in the doubly linked list, holding:

  • cnt which represents the count of the keys in the node.
  • keys a set of keys that have the same count.
  • prev and next pointers used to link with other nodes in the list.

The Node class also provides methods such as insert to insert a new node after the current node and remove to unlink the current node from the list.

AllOne Class

Upon initialising (__init__) the AllOne class, a circular doubly linked list is created with a sentinel root node to simplify insertions and deletions.

Incrementing Counts (inc)

  • When incrementing the count of a key using the inc method:

    • If the key is new, check if there is a node right after root with a count of 1:

      • If there is, add the key to that node's keys set.
      • If there isn't, insert a new node after root with count 1 and add the key to that new node's keys set.

    • If the key exists in a node, then:

      • Check if the next node represents the incremented count:
        • If it does, add the key to the next node's keys set.
        • If it doesn't, insert a new node with the incremented count right after the current one.

Decrementing Counts (dec)

  • To decrement the count using the dec method:

    • If the count after decrement would be 0, remove the key from the hashtable.

    • If the key's count after decrementing matches the count of the previous node:

      • Add the key to the previous node's keys set.

    • If it doesn't match the previous node's count or the previous is the root, create a new node with the decremented count and insert it before the current node.

Retrieving Maximum and Minimum Keys (getMaxKey and getMinKey)

  • getMaxKey: The maximum key is present in the keys set of the node right before the root node (since the list is sorted with the maximum count at the end).

  • getMinKey: The minimum key is present in the keys set of the node right after the root node (since the list is sorted with the minimum count at the beginning).

Throughout the process, after any increment or decrement operation, if the keys set of a node becomes empty, that node is removed from the list to maintain the integrity of counts.

Following these steps ensures that all the required operations are done in average O(1) time complexity, satisfying the problem's constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

  1. Initialize the AllOne data structure:

    • A root node is created, which is a sentinel node for our doubly linked list.

  2. inc("apple") Operation:

    • Since "apple" is new and there is no node with count 1 right after the root, we insert a new node with count 1 after root and add "apple" to this node's keys set.
    • Now our list looks like: root <-> Node(count=1, keys={"apple"}) <-> root (back to root, it's circular)

  3. inc("banana") Operation:

    • The "banana" key is also new. Similarly, we insert "banana" in the same node as "apple" because it has a count of 1.
    • The list stays the same but now the node has both "apple" and "banana": root <-> Node(count=1, keys={"apple", "banana"}) <-> root

  4. inc("apple") Operation:

    • Now, "apple" exists, and its count should be incremented to 2.
    • We check the next node. Since there isn’t a node with count 2, we create a new node with count 2 and move "apple" to this new node's keys set.
    • Our list is now: root <-> Node(count=1, keys={"banana"}) <-> Node(count=2, keys={"apple"}) <-> root

  5. dec("banana") Operation:

    • We decrement the count of "banana". If it becomes 0, we have to remove it completely.
    • Since the node with "banana" will have a count of 0 and there is no node before it (other than root), "banana" is removed from the list and the hashtable.
    • The list remains: root <-> Node(count=2, keys={"apple"}) <-> root

  6. getMaxKey() Operation:

    • We find the max key which should be in the node right before root which has "apple" with count 2.
    • The maximum key is "apple".

  7. getMinKey() Operation:

    • Since the node with "banana" is removed, the minimum count node is also the one with "apple". So, "apple" is the minimum key too.

Here you can see how incrementing, decrementing, and getting max and min keys are all performed in constant O(1) average time by maintaining an orderly doubly linked list and hashtable. After each operation, we ensure the integrity of the counts by adding or removing nodes or keys as necessary.

Solution Implementation

1class Node:
2    def __init__(self, key='', count=0):
3        self.prev = None
4        self.next = None
5        self.count = count  # The number of times this key appears
6        self.keys = {key}  # A set of keys with the same count
7
8    def insert(self, node):
9        """Insert the given node after this node."""
10        node.prev = self
11        node.next = self.next
12        self.next.prev = node
13        self.next = node
14        return node
15
16    def remove(self):
17        """Remove this node from the list."""
18        self.prev.next = self.next
19        self.next.prev = self.prev
20
21
22class AllOne:
23    def __init__(self):
24        self.root = Node()  # Dummy root node of the doubly linked list
25        self.root.next = self.root  # Initialize root to point to itself
26        self.root.prev = self.root
27        self.nodes = {}  # Key to node dictionary
28
29    def inc(self, key: str) -> None:
30        """Increase the count of the key by 1."""
31        if key not in self.nodes:
32            # Key not in list, so add with count 1
33            if self.root.next == self.root or self.root.next.count > 1:
34                # Insert new node after root if next node's count is more than 1
35                self.nodes[key] = self.root.insert(Node(key, 1))
36            else:
37                # Otherwise, add the key to the next node's keys
38                self.root.next.keys.add(key)
39                self.nodes[key] = self.root.next
40        else:
41            current = self.nodes[key]
42            next_node = current.next
43            if next_node == self.root or next_node.count > current.count + 1:
44                # Insert new node if there's no node for count = current.count + 1
45                self.nodes[key] = current.insert(Node(key, current.count + 1))
46            else:
47                next_node.keys.add(key)
48                self.nodes[key] = next_node
49            current.keys.discard(key)
50            if not current.keys:
51                # Remove current node if there are no keys left in it
52                current.remove()
53
54    def dec(self, key: str) -> None:
55        """Decrease the count of the key by 1."""
56        current = self.nodes[key]
57        if current.count == 1:
58            # Remove the key if its count goes to 0
59            del self.nodes[key]
60        else:
61            previous = current.prev
62            if previous == self.root or previous.count < current.count - 1:
63                # Insert new node if there's no node for count = current.count - 1
64                self.nodes[key] = previous.insert(Node(key, current.count - 1))
65            else:
66                # Otherwise, add the key to the previous node's keys
67                previous.keys.add(key)
68                self.nodes[key] = previous
69        current.keys.discard(key)
70        if not current.keys:
71            # Remove current node if there are no keys left in it
72            current.remove()
73
74    def getMaxKey(self) -> str:
75        """Return a key with the highest count. If no keys are present, return an empty string."""
76        if self.root.prev == self.root:
77            return ""  # The list is empty
78        return next(iter(self.root.prev.keys))
79
80    def getMinKey(self) -> str:
81        """Return a key with the lowest count. If no keys are present, return an empty string."""
82        if self.root.next == self.root:
83            return ""  # The list is empty
84        return next(iter(self.root.next.keys))
85
86# Your AllOne object will be instantiated and called as such:
87# obj = AllOne()
88# obj.inc(key)
89# obj.dec(key)
90# max_key = obj.getMaxKey()
91# min_key = obj.getMinKey()
92
1import java.util.HashMap;
2import java.util.HashSet;
3import java.util.Iterator;
4import java.util.Map;
5import java.util.Set;
6
7class AllOne {
8    private final Node root = new Node(); // Sentinel node to mark beginning and end of doubly linked list
9    private final Map<String, Node> nodes = new HashMap<>(); // Mapping from key to its corresponding Node
10
11    public AllOne() {
12        // Initialize the doubly linked list with root node pointing to itself
13        root.next = root;
14        root.prev = root;
15    }
16
17    public void inc(String key) {
18        // Increase the count for the key
19        if (!nodes.containsKey(key)) {
20            // If key is new, insert it appropriately
21            if (root.next == root || root.next.cnt > 1) {
22                nodes.put(key, root.insert(new Node(key, 1)));
23            } else {
24                root.next.keys.add(key);
25                nodes.put(key, root.next);
26            }
27        } else {
28            // If key already exists, move it to the next Node or create a new Node
29            Node current = nodes.get(key);
30            Node next = current.next;
31            if (next == root || next.cnt > current.cnt + 1) {
32                nodes.put(key, current.insert(new Node(key, current.cnt + 1)));
33            } else {
34                next.keys.add(key);
35                nodes.put(key, next);
36            }
37            // Remove key from current Node and check if it should be deleted
38            current.keys.remove(key);
39            if (current.keys.isEmpty()) {
40                current.remove();
41            }
42        }
43    }
44
45    public void dec(String key) {
46        // Decrease the count for the key
47        Node current = nodes.get(key);
48        if (current.cnt == 1) {
49            // If count goes to 0, remove key from system
50            nodes.remove(key);
51        } else {
52            // Move key to the previous Node or create a new Node
53            Node prev = current.prev;
54            if (prev == root || prev.cnt < current.cnt - 1) {
55                nodes.put(key, prev.insert(new Node(key, current.cnt - 1)));
56            } else {
57                prev.keys.add(key);
58                nodes.put(key, prev);
59            }
60        }
61      
62        // Remove key from current Node and remove Node if empty
63        current.keys.remove(key);
64        if (current.keys.isEmpty()) {
65            current.remove();
66        }
67    }
68
69    public String getMaxKey() {
70        // Get and return a key with the maximum count
71        if (root.prev == root) return ""; // Handle case with no keys
72        return root.prev.keys.iterator().next();
73    }
74
75    public String getMinKey() {
76        // Get and return a key with the minimum count
77        if (root.next == root) return ""; // Handle case with no keys
78        return root.next.keys.iterator().next();
79    }
80}
81
82class Node {
83    Node prev; // Previous node in doubly linked list
84    Node next; // Next node in doubly linked list
85    int cnt; // Count associated with node
86    Set<String> keys = new HashSet<>(); // Set of keys with this count
87
88    // Constructor for sentinel node
89    public Node() {
90        this("", 0);
91    }
92
93    // Constructor for actual nodes
94    public Node(String key, int cnt) {
95        this.cnt = cnt;
96        keys.add(key);
97    }
98
99    // Method to insert this node before the provided node
100    public Node insert(Node node) {
101        node.prev = this;
102        node.next = this.next;
103        node.prev.next = node;
104        node.next.prev = node;
105        return node;
106    }
107
108    // Method to remove this node from the linked list
109    public void remove() {
110        this.prev.next = this.next;
111        this.next.prev = this.prev;
112    }
113}
114
1#include <unordered_map>
2#include <unordered_set>
3#include <string>
4
5class Node {
6public:
7    Node *prev; // Pointer to the previous node in the doubly linked list
8    Node *next; // Pointer to the next node in the doubly linked list
9    int count; // Count of occurrences for this node
10    std::unordered_set<std::string> keys; // Set of keys with this occurrence count
11
12    // Constructor for sentinel node
13    Node() : prev(nullptr), next(nullptr), count(0) {}
14
15    // Constructor for actual nodes with a given key and count
16    Node(const std::string& key, int count) : prev(nullptr), next(nullptr), count(count) {
17        keys.insert(key);
18    }
19
20    // Method to insert a node after this node
21    Node* insert(Node* node) {
22        node->prev = this;
23        node->next = this->next;
24        this->next->prev = node;
25        this->next = node;
26        return node;
27    }
28
29    // Remove the node from the doubly linked list
30    void remove() {
31        this->prev->next = this->next;
32        this->next->prev = this->prev;
33    }
34};
35
36class AllOne {
37private:
38    Node root; // Sentinel node to mark the beginning and end of the doubly linked list
39    std::unordered_map<std::string, Node*> nodes; // Mapping from keys to their corresponding nodes
40
41public:
42    AllOne() {
43        // Initialize the doubly linked list with the sentinel node linking to itself
44        root.next = &root;
45        root.prev = &root;
46    }
47
48    void inc(const std::string& key) {
49        // Increase the count for the key
50        if (nodes.find(key) == nodes.end()) {
51            // If key is new, insert it into the list
52            if (root.next == &root || root.next->count > 1) {
53                nodes[key] = root.insert(new Node(key, 1));
54            } else {
55                root.next->keys.insert(key);
56                nodes[key] = root.next;
57            }
58        } else {
59            // If the key already exists, move it to a new or next existing Node
60            Node *current = nodes[key];
61            Node *next = current->next;
62            if (next == &root || next->count > current->count + 1) {
63                nodes[key] = current->insert(new Node(key, current->count + 1));
64            } else {
65                next->keys.insert(key);
66                nodes[key] = next;
67            }
68            // Remove the key from the current Node and delete the Node if it's empty
69            current->keys.erase(key);
70            if (current->keys.empty()) {
71                current->remove();
72                delete current; // C++ requires explicit deletion
73            }
74        }
75    }
76
77    void dec(const std::string& key) {
78        auto it = nodes.find(key);
79        if (it == nodes.end()) return;
80        Node *current = it->second;
81        if (current->count == 1) {
82            // Remove the key completely if the count is 1
83            nodes.erase(key);
84        } else {
85            // Move the key to previous Node or create a new Node
86            Node *prev = current->prev;
87            if (prev == &root || prev->count < current->count - 1) {
88                nodes[key] = prev->insert(new Node(key, current->count - 1));
89            } else {
90                prev->keys.insert(key);
91                nodes[key] = prev;
92            }
93        }
94        // Remove the key from the current Node and delete the Node if empty
95        current->keys.erase(key);
96        if (current->keys.empty()) {
97            current->remove();
98            delete current; // C++ requires explicit deletion
99        }
100    }
101
102    std::string getMaxKey() {
103        // Return a key with the maximum count
104        if (root.prev == &root) return ""; // Handle case with no keys
105        return *root.prev->keys.begin();
106    }
107
108    std::string getMinKey() {
109        // Return a key with the minimum count
110        if (root.next == &root) return ""; // Handle case with no keys
111        return *root.next->keys.begin();
112    }
113};
114
1// Define a Node class to represent each entry in our linked list
2class Node {
3    prev: Node | null; // Reference to the previous node in the list
4    next: Node | null; // Reference to the next node in the list
5    count: number; // Number of occurrences of keys
6    keys: Set<string>; // Set of keys with this occurrence count
7
8    // Constructor to initialize a new instance of Node
9    constructor(key: string = "", count: number = 0) {
10        this.prev = this.next = null;
11        this.count = count;
12        this.keys = new Set(key ? [key] : []);
13    }
14
15    // Method to insert a new node after the current node
16    insertAfter(newNode: Node): Node {
17        newNode.prev = this;
18        newNode.next = this.next;
19        if (this.next) {
20            this.next.prev = newNode;
21        }
22        this.next = newNode;
23        return newNode;
24    }
25
26    // Method to remove the current node from the list
27    removeFromList(): void {
28        if (this.prev) {
29            this.prev.next = this.next;
30        }
31        if (this.next) {
32            this.next.prev = this.prev;
33        }
34    }
35}
36
37// Create a sentinel node as the root node of our doubly linked list
38const root = new Node();
39
40// Initialize root to point to itself, creating an empty linked list
41root.prev = root;
42root.next = root;
43
44// Create a mapping from key to its corresponding node
45const nodes: Map<string, Node> = new Map();
46
47// Function to increment the occurrence count of a key
48function incrementKey(key: string): void {
49    if (!nodes.has(key)) {
50        // Handle new key
51        insertNewKey(key);
52    } else {
53        // Handle existing key
54        incrementExistingKey(key);
55    }
56}
57
58// Function to decrement the occurrence count of a key
59function decrementKey(key: string): void {
60    const current = nodes.get(key);
61    if (!current) return;
62
63    if (current.count === 1) {
64        // Remove the key if its count reaches zero
65        nodes.delete(key);
66        current.keys.delete(key);
67    } else {
68        // Move the key to a lower count or create a new node if necessary
69        moveToPreviousCount(key, current);
70    }
71    // Remove node if it's empty
72    if (current.keys.size === 0) {
73        current.removeFromList();
74    }
75}
76
77// Function to retrieve a key with the maximum count
78function getMaxKey(): string {
79    // If list is empty, return an empty string
80    if (root.prev === root) return "";
81    return root.prev.keys.values().next().value;
82}
83
84// Function to retrieve a key with the minimum count
85function getMinKey(): string {
86    // If list is empty, return an empty string
87    if (root.next === root) return "";
88    return root.next.keys.values().next().value;
89}
90
91// ... (additional helper functions such as `insertNewKey`, `incrementExistingKey`, `moveToPreviousCount` would be implemented here)
92
93// (The remaining helpers and logic can be implemented following the below pattern):
94// Implement helper methods such as `insertNewKey`, `incrementExistingKey`, and `moveToPreviousCount`
95// which follow the logic outlined in the provided Java code. These helpers manage the linked list
96// and the nodes map, ensuring that keys are correctly incremented or decremented in counts and
97// the corresponding nodes are inserted or removed as needed within the list structure.
98
Not Sure What to Study? Take the 2-min Quiz：

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

Time Complexity:

  • __init__: O(1), since it simply initializes a few variables, including the root node.
  • inc:
    • O(1) for key absence because it's either adding a new node immediately after the root or to the existing minimum node.
    • O(1) for key presence because it involves operations that are constant time: updating a set of keys, potentially inserting a node in a doubly-linked list, and possibly removing a node if the key set becomes empty.
  • dec:
    • O(1) for decreasing the count, similar reasons as in inc, with potentially inserting a node before the current one if the decremented count doesn't match the previous node's count, or updating the key set.
    • O(1) for removing the key if its count reaches 1 and updating the node set.
    • O(1) for the actual node removal if there are no more keys left in the node.
  • getMaxKey and getMinKey: O(1), as it involves accessing the max or min node (which is either root.prev or root.next) and then getting the first element from the keys set.

Space Complexity:

  • O(N) where N is the number of unique keys stored in the data structure.
    • Each unique key can be in a Node, and each Node has a corresponding entry in the nodes hash table, plus the doubly linked list nodes that are predefined in the structure. There's a fixed number of pointers and an additional set in each Node that contains the keys with the same count.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫