Facebook Pixel

432. All O`one Data Structure

HardDesignHash TableLinked ListDoubly-Linked List
Leetcode Link

Problem Description

This problem asks you to design a data structure called AllOne that maintains string counts and can efficiently retrieve strings with minimum and maximum counts.

The data structure needs to support the following operations:

  1. AllOne(): Initialize an empty data structure.

  2. inc(String key): Increase the count of string key by 1. If key doesn't exist yet, add it with count 1.

  3. dec(String key): Decrease the count of string key by 1. If the count reaches 0, remove the string from the data structure. The problem guarantees that key exists when dec is called.

  4. getMaxKey(): Return any string that has the maximum count. Return "" if the data structure is empty.

  5. getMinKey(): Return any string that has the minimum count. Return "" if the data structure is empty.

Critical Constraint: All operations must run in O(1) average time complexity.

The challenge lies in maintaining the ability to track both minimum and maximum counts while supporting increment and decrement operations, all in constant time. A simple hash map wouldn't suffice since finding min/max would require O(n) time. The solution uses a doubly-linked list where each node represents a count value and contains all strings with that count, combined with a hash map for O(1) access to each string's node. This allows all operations to maintain O(1) complexity by organizing strings by their counts in sorted order within the linked list structure.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight starts with recognizing that we need O(1) access to both minimum and maximum count strings. A simple hash map {key: count} gives us O(1) increment/decrement but finding min/max would require scanning all entries in O(n) time.

To achieve O(1) min/max retrieval, we need to maintain some ordering. But traditional sorted structures like balanced trees give us O(log n) operations, not O(1).

The breakthrough comes from observing that counts change incrementally - when we increment a key, its count goes from n to n+1, and when we decrement, it goes from n to n-1. We never jump directly from count 2 to count 10.

This incremental nature suggests using a doubly-linked list where each node represents a specific count value (1, 2, 3, ...) and maintains all strings having that count. The nodes are ordered by count value.

Why does this work for O(1)?

  • When incrementing a string with count n, we only need to check if a node with count n+1 exists right after the current node. If it does, move the string there; if not, create a new node.
  • Similarly for decrement, we check for count n-1 node right before.
  • The min count strings are always in the first node after the dummy head.
  • The max count strings are always in the last node before the dummy head.

We maintain a hash map {key: node} to directly access which node contains each string in O(1). The doubly-linked list with a circular dummy head makes insertion/removal operations clean and avoids edge cases.

Each count value appears at most once in the list, and strings with the same count are grouped together in a set within their node. When a node's set becomes empty (no strings with that count), we remove the node entirely.

Solution Approach

The solution uses a doubly-linked list of nodes where each node represents a unique count value and stores all strings with that count. Additionally, a hash map tracks which node each string belongs to.

Data Structures:

  1. Node Class: Each node contains:

    • cnt: The count value this node represents
    • keys: A set of all strings with this count
    • prev and next: Pointers for the doubly-linked list
    • Helper methods insert() to add a new node after this one, and remove() to unlink this node

  2. AllOne Class: Contains:

    • root: A dummy sentinel node that makes the list circular (root.next points to min count node, root.prev points to max count node)
    • nodes: A hash map {string: node} for O(1) access to each string's current node

Implementation Details:

inc(key):

  1. If key is new:
    • Check if the first node after root exists and has count 1
    • If yes, add key to that node's set
    • If no, create a new node with count 1 and insert it after root
  2. If key exists:
    • Get current node from nodes[key]
    • Check if next node has count curr.cnt + 1
    • If yes, move key to that node
    • If no, create a new node with count curr.cnt + 1 and insert it
    • Remove key from current node's set
    • If current node becomes empty, remove it from the list

dec(key):

  1. Get current node from nodes[key]
  2. If count becomes 0 (curr.cnt == 1):
    • Remove key from nodes map entirely
  3. Otherwise:
    • Check if previous node has count curr.cnt - 1
    • If yes, move key to that node
    • If no, create a new node with count curr.cnt - 1 and insert it
  4. Remove key from current node's set
  5. If current node becomes empty, remove it from the list

getMinKey() and getMaxKey():

  • Min: Return any key from root.next.keys (first node after dummy)
  • Max: Return any key from root.prev.keys (last node before dummy)
  • Both use next(iter(set)) to get an arbitrary element from the set in O(1)

The circular dummy node elegantly handles edge cases - when the list is empty, root.next == root.prev == root, and both min/max operations return empty string as required.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a sequence of operations to see how the data structure maintains O(1) operations:

Initial state: Empty structure with just the dummy root node pointing to itself.

root ↔ root (circular)
nodes = {}

Operation 1: inc("apple")

  • "apple" is new, need a node with count 1
  • Create new node with count=1, insert after root
  • Add "apple" to this node's key set
root ↔ [count:1, keys:{"apple"}] ↔ root
nodes = {"apple": node1}

Operation 2: inc("banana")

  • "banana" is new, check if first node has count 1 (yes!)
  • Add "banana" to existing count=1 node
root ↔ [count:1, keys:{"apple","banana"}] ↔ root
nodes = {"apple": node1, "banana": node1}

Operation 3: inc("apple")

  • "apple" exists in count=1 node
  • Check if next node has count=2 (no, next is root)
  • Create new node with count=2, insert after count=1 node
  • Move "apple" from count=1 to count=2
root ↔ [count:1, keys:{"banana"}] ↔ [count:2, keys:{"apple"}] ↔ root
nodes = {"apple": node2, "banana": node1}

Operation 4: getMinKey()

  • Return any key from root.next (first node)
  • Returns "banana" (count=1)

Operation 5: getMaxKey()

  • Return any key from root.prev (last node)
  • Returns "apple" (count=2)

Operation 6: dec("banana")

  • "banana" is in count=1 node
  • Count becomes 0, so remove "banana" entirely
  • Count=1 node becomes empty, remove it from list
root ↔ [count:2, keys:{"apple"}] ↔ root
nodes = {"apple": node2}

Operation 7: inc("apple")

  • "apple" is in count=2 node
  • Check if next node has count=3 (no, next is root)
  • Create new node with count=3, insert after count=2 node
  • Move "apple" to count=3, count=2 node becomes empty and is removed
root ↔ [count:3, keys:{"apple"}] ↔ root
nodes = {"apple": node3}

Notice how each operation only involves:

  • Looking up a key in the hash map: O(1)
  • Checking immediate neighbors (prev/next): O(1)
  • Adding/removing from a set: O(1)
  • Inserting/removing a node: O(1)

The doubly-linked list maintains counts in sorted order, but we never traverse it - we only look at immediate neighbors when incrementing/decrementing, and at the ends for min/max operations.

Solution Implementation

1class Node:
2    """
3    Represents a node in the doubly-linked list.
4    Each node stores a count value and all keys that have that count.
5    """
6    def __init__(self, key: str = '', count: int = 0):
7        self.prev = None  # Previous node in the linked list
8        self.next = None  # Next node in the linked list
9        self.count = count  # The count value this node represents
10        self.keys = {key} if key else set()  # Set of keys with this count
11  
12    def insert_after(self, new_node: 'Node') -> 'Node':
13        """
14        Insert a new node right after the current node.
15        Returns the newly inserted node.
16        """
17        new_node.prev = self
18        new_node.next = self.next
19        self.next.prev = new_node
20        self.next = new_node
21        return new_node
22  
23    def remove(self) -> None:
24        """
25        Remove this node from the linked list by connecting 
26        its previous and next nodes directly.
27        """
28        self.prev.next = self.next
29        self.next.prev = self.prev
30
31
32class AllOne:
33    """
34    A data structure that maintains string keys with their counts.
35    Supports incrementing/decrementing counts and retrieving keys with min/max counts.
36    All operations run in O(1) time.
37    """
38    def __init__(self):
39        # Create a sentinel root node for the circular doubly-linked list
40        self.root = Node()
41        self.root.next = self.root
42        self.root.prev = self.root
43      
44        # Map each key to its corresponding node in the linked list
45        self.key_to_node = {}
46  
47    def inc(self, key: str) -> None:
48        """
49        Increment the count of the given key by 1.
50        If the key doesn't exist, initialize it with count 1.
51        """
52        if key not in self.key_to_node:
53            # Key doesn't exist, need to add it with count 1
54            if self.root.next == self.root or self.root.next.count > 1:
55                # No node with count 1 exists, create a new one
56                new_node = Node(key, 1)
57                self.key_to_node[key] = self.root.insert_after(new_node)
58            else:
59                # Node with count 1 already exists, add key to it
60                self.root.next.keys.add(key)
61                self.key_to_node[key] = self.root.next
62        else:
63            # Key exists, increment its count
64            current_node = self.key_to_node[key]
65            next_node = current_node.next
66            new_count = current_node.count + 1
67          
68            # Check if we need to create a new node for the incremented count
69            if next_node == self.root or next_node.count > new_count:
70                # Create new node with incremented count
71                new_node = Node(key, new_count)
72                self.key_to_node[key] = current_node.insert_after(new_node)
73            else:
74                # Node with the target count already exists
75                next_node.keys.add(key)
76                self.key_to_node[key] = next_node
77          
78            # Remove key from current node
79            current_node.keys.discard(key)
80            if not current_node.keys:
81                # If node has no keys left, remove it from the list
82                current_node.remove()
83  
84    def dec(self, key: str) -> None:
85        """
86        Decrement the count of the given key by 1.
87        If the count reaches 0, remove the key entirely.
88        Assumes the key exists in the data structure.
89        """
90        current_node = self.key_to_node[key]
91      
92        if current_node.count == 1:
93            # Count will become 0, remove the key entirely
94            del self.key_to_node[key]
95        else:
96            # Decrement the count
97            prev_node = current_node.prev
98            new_count = current_node.count - 1
99          
100            # Check if we need to create a new node for the decremented count
101            if prev_node == self.root or prev_node.count < new_count:
102                # Create new node with decremented count
103                new_node = Node(key, new_count)
104                self.key_to_node[key] = prev_node.insert_after(new_node)
105            else:
106                # Node with the target count already exists
107                prev_node.keys.add(key)
108                self.key_to_node[key] = prev_node
109      
110        # Remove key from current node
111        current_node.keys.discard(key)
112        if not current_node.keys:
113            # If node has no keys left, remove it from the list
114            current_node.remove()
115  
116    def getMaxKey(self) -> str:
117        """
118        Return a key with the maximum count.
119        If multiple keys have the maximum count, return any one of them.
120        Returns empty string if no keys exist.
121        """
122        if self.root.prev == self.root:
123            return ""
124        # The last node (root.prev) contains keys with maximum count
125        return next(iter(self.root.prev.keys))
126  
127    def getMinKey(self) -> str:
128        """
129        Return a key with the minimum count.
130        If multiple keys have the minimum count, return any one of them.
131        Returns empty string if no keys exist.
132        """
133        if self.root.next == self.root:
134            return ""
135        # The first node (root.next) contains keys with minimum count
136        return next(iter(self.root.next.keys))
137
138
139# Your AllOne object will be instantiated and called as such:
140# obj = AllOne()
141# obj.inc(key)
142# obj.dec(key)
143# param_3 = obj.getMaxKey()
144# param_4 = obj.getMinKey()
145
1/**
2 * Data structure that maintains string counts and provides O(1) operations for:
3 * - Incrementing/decrementing a string's count
4 * - Getting the string with minimum/maximum count
5 * 
6 * Uses a doubly-linked list of buckets (nodes) where each bucket contains
7 * all strings with the same count, ordered by count value.
8 */
9class AllOne {
10    // Sentinel node for the doubly-linked list (acts as both head and tail marker)
11    private Node sentinel;
12  
13    // Maps each string key to its corresponding bucket node
14    private Map<String, Node> keyToNodeMap;
15
16    /**
17     * Initializes the data structure with an empty sentinel node
18     */
19    public AllOne() {
20        sentinel = new Node();
21        sentinel.next = sentinel;
22        sentinel.prev = sentinel;
23        keyToNodeMap = new HashMap<>();
24    }
25
26    /**
27     * Increments the count of the given key by 1
28     * If key doesn't exist, initializes it with count 1
29     * 
30     * @param key The string key to increment
31     */
32    public void inc(String key) {
33        if (!keyToNodeMap.containsKey(key)) {
34            // Key doesn't exist - add it with count 1
35            if (sentinel.next == sentinel || sentinel.next.count > 1) {
36                // Need to create a new node with count 1
37                Node newNode = new Node(key, 1);
38                keyToNodeMap.put(key, sentinel.insertAfter(newNode));
39            } else {
40                // A node with count 1 already exists
41                sentinel.next.keys.add(key);
42                keyToNodeMap.put(key, sentinel.next);
43            }
44        } else {
45            // Key exists - increment its count
46            Node currentNode = keyToNodeMap.get(key);
47            Node nextNode = currentNode.next;
48            int newCount = currentNode.count + 1;
49          
50            if (nextNode == sentinel || nextNode.count > newCount) {
51                // Need to create a new node with the incremented count
52                Node newNode = new Node(key, newCount);
53                keyToNodeMap.put(key, currentNode.insertAfter(newNode));
54            } else {
55                // A node with the target count already exists
56                nextNode.keys.add(key);
57                keyToNodeMap.put(key, nextNode);
58            }
59          
60            // Remove key from current node and clean up if empty
61            currentNode.keys.remove(key);
62            if (currentNode.keys.isEmpty()) {
63                currentNode.removeFromList();
64            }
65        }
66    }
67
68    /**
69     * Decrements the count of the given key by 1
70     * If count reaches 0, removes the key entirely
71     * Assumes the key exists in the data structure
72     * 
73     * @param key The string key to decrement
74     */
75    public void dec(String key) {
76        Node currentNode = keyToNodeMap.get(key);
77      
78        if (currentNode.count == 1) {
79            // Count becomes 0 - remove the key entirely
80            keyToNodeMap.remove(key);
81        } else {
82            // Decrement the count
83            Node previousNode = currentNode.prev;
84            int newCount = currentNode.count - 1;
85          
86            if (previousNode == sentinel || previousNode.count < newCount) {
87                // Need to create a new node with the decremented count
88                Node newNode = new Node(key, newCount);
89                keyToNodeMap.put(key, previousNode.insertAfter(newNode));
90            } else {
91                // A node with the target count already exists
92                previousNode.keys.add(key);
93                keyToNodeMap.put(key, previousNode);
94            }
95        }
96      
97        // Remove key from current node and clean up if empty
98        currentNode.keys.remove(key);
99        if (currentNode.keys.isEmpty()) {
100            currentNode.removeFromList();
101        }
102    }
103
104    /**
105     * Returns one of the keys with the maximum count
106     * Returns empty string if the data structure is empty
107     * 
108     * @return A string with maximum count, or empty string if none exists
109     */
110    public String getMaxKey() {
111        if (sentinel.prev == sentinel) {
112            return "";
113        }
114        return sentinel.prev.keys.iterator().next();
115    }
116
117    /**
118     * Returns one of the keys with the minimum count
119     * Returns empty string if the data structure is empty
120     * 
121     * @return A string with minimum count, or empty string if none exists
122     */
123    public String getMinKey() {
124        if (sentinel.next == sentinel) {
125            return "";
126        }
127        return sentinel.next.keys.iterator().next();
128    }
129}
130
131/**
132 * Node class representing a bucket in the doubly-linked list
133 * Each node contains all strings with the same count value
134 */
135class Node {
136    // Previous and next pointers for doubly-linked list
137    Node prev;
138    Node next;
139  
140    // The count value for all strings in this bucket
141    int count;
142  
143    // Set of all string keys with this count value
144    Set<String> keys;
145
146    /**
147     * Default constructor for creating the sentinel node
148     */
149    public Node() {
150        this("", 0);
151    }
152
153    /**
154     * Constructor for creating a node with a specific key and count
155     * 
156     * @param key The initial key to add to this bucket
157     * @param count The count value for this bucket
158     */
159    public Node(String key, int count) {
160        this.count = count;
161        this.keys = new HashSet<>();
162        if (!key.isEmpty()) {
163            this.keys.add(key);
164        }
165    }
166
167    /**
168     * Inserts a new node immediately after this node in the linked list
169     * 
170     * @param nodeToInsert The node to insert after this node
171     * @return The inserted node
172     */
173    public Node insertAfter(Node nodeToInsert) {
174        nodeToInsert.prev = this;
175        nodeToInsert.next = this.next;
176        this.next.prev = nodeToInsert;
177        this.next = nodeToInsert;
178        return nodeToInsert;
179    }
180
181    /**
182     * Removes this node from the doubly-linked list
183     */
184    public void removeFromList() {
185        this.prev.next = this.next;
186        this.next.prev = this.prev;
187    }
188}
189
190/**
191 * Your AllOne object will be instantiated and called as such:
192 * AllOne obj = new AllOne();
193 * obj.inc(key);
194 * obj.dec(key);
195 * String param_3 = obj.getMaxKey();
196 * String param_4 = obj.getMinKey();
197 */
198
1/**
2 * Data structure that maintains string counts and provides O(1) operations for:
3 * - Incrementing/decrementing a string's count
4 * - Getting the string with minimum/maximum count
5 * 
6 * Uses a doubly-linked list of buckets (nodes) where each bucket contains
7 * all strings with the same count, ordered by count value.
8 */
9class AllOne {
10private:
11    /**
12     * Node class representing a bucket in the doubly-linked list
13     * Each node contains all strings with the same count value
14     */
15    struct Node {
16        // Previous and next pointers for doubly-linked list
17        Node* prev;
18        Node* next;
19      
20        // The count value for all strings in this bucket
21        int count;
22      
23        // Set of all string keys with this count value
24        unordered_set<string> keys;
25      
26        /**
27         * Constructor for creating a node with a specific count
28         * 
29         * @param cnt The count value for this bucket
30         */
31        Node(int cnt = 0) : count(cnt), prev(nullptr), next(nullptr) {}
32      
33        /**
34         * Inserts a new node immediately after this node in the linked list
35         * 
36         * @param node_to_insert The node to insert after this node
37         * @return The inserted node
38         */
39        Node* insertAfter(Node* node_to_insert) {
40            node_to_insert->prev = this;
41            node_to_insert->next = this->next;
42            this->next->prev = node_to_insert;
43            this->next = node_to_insert;
44            return node_to_insert;
45        }
46      
47        /**
48         * Removes this node from the doubly-linked list
49         */
50        void removeFromList() {
51            this->prev->next = this->next;
52            this->next->prev = this->prev;
53        }
54    };
55  
56    // Sentinel node for the doubly-linked list (acts as both head and tail marker)
57    Node* sentinel;
58  
59    // Maps each string key to its corresponding bucket node
60    unordered_map<string, Node*> key_to_node_map;
61  
62public:
63    /**
64     * Initializes the data structure with an empty sentinel node
65     */
66    AllOne() {
67        sentinel = new Node();
68        sentinel->next = sentinel;
69        sentinel->prev = sentinel;
70    }
71  
72    /**
73     * Destructor to clean up allocated memory
74     */
75    ~AllOne() {
76        Node* current = sentinel->next;
77        while (current != sentinel) {
78            Node* next = current->next;
79            delete current;
80            current = next;
81        }
82        delete sentinel;
83    }
84  
85    /**
86     * Increments the count of the given key by 1
87     * If key doesn't exist, initializes it with count 1
88     * 
89     * @param key The string key to increment
90     */
91    void inc(string key) {
92        if (key_to_node_map.find(key) == key_to_node_map.end()) {
93            // Key doesn't exist - add it with count 1
94            if (sentinel->next == sentinel || sentinel->next->count > 1) {
95                // Need to create a new node with count 1
96                Node* new_node = new Node(1);
97                new_node->keys.insert(key);
98                key_to_node_map[key] = sentinel->insertAfter(new_node);
99            } else {
100                // A node with count 1 already exists
101                sentinel->next->keys.insert(key);
102                key_to_node_map[key] = sentinel->next;
103            }
104        } else {
105            // Key exists - increment its count
106            Node* current_node = key_to_node_map[key];
107            Node* next_node = current_node->next;
108            int new_count = current_node->count + 1;
109          
110            if (next_node == sentinel || next_node->count > new_count) {
111                // Need to create a new node with the incremented count
112                Node* new_node = new Node(new_count);
113                new_node->keys.insert(key);
114                key_to_node_map[key] = current_node->insertAfter(new_node);
115            } else {
116                // A node with the target count already exists
117                next_node->keys.insert(key);
118                key_to_node_map[key] = next_node;
119            }
120          
121            // Remove key from current node and clean up if empty
122            current_node->keys.erase(key);
123            if (current_node->keys.empty()) {
124                current_node->removeFromList();
125                delete current_node;
126            }
127        }
128    }
129  
130    /**
131     * Decrements the count of the given key by 1
132     * If count reaches 0, removes the key entirely
133     * Assumes the key exists in the data structure
134     * 
135     * @param key The string key to decrement
136     */
137    void dec(string key) {
138        if (key_to_node_map.find(key) == key_to_node_map.end()) {
139            return; // Key doesn't exist
140        }
141      
142        Node* current_node = key_to_node_map[key];
143      
144        if (current_node->count == 1) {
145            // Count becomes 0 - remove the key entirely
146            key_to_node_map.erase(key);
147        } else {
148            // Decrement the count
149            Node* previous_node = current_node->prev;
150            int new_count = current_node->count - 1;
151          
152            if (previous_node == sentinel || previous_node->count < new_count) {
153                // Need to create a new node with the decremented count
154                Node* new_node = new Node(new_count);
155                new_node->keys.insert(key);
156                key_to_node_map[key] = previous_node->insertAfter(new_node);
157            } else {
158                // A node with the target count already exists
159                previous_node->keys.insert(key);
160                key_to_node_map[key] = previous_node;
161            }
162        }
163      
164        // Remove key from current node and clean up if empty
165        current_node->keys.erase(key);
166        if (current_node->keys.empty()) {
167            current_node->removeFromList();
168            delete current_node;
169        }
170    }
171  
172    /**
173     * Returns one of the keys with the maximum count
174     * Returns empty string if the data structure is empty
175     * 
176     * @return A string with maximum count, or empty string if none exists
177     */
178    string getMaxKey() {
179        if (sentinel->prev == sentinel) {
180            return "";
181        }
182        return *(sentinel->prev->keys.begin());
183    }
184  
185    /**
186     * Returns one of the keys with the minimum count
187     * Returns empty string if the data structure is empty
188     * 
189     * @return A string with minimum count, or empty string if none exists
190     */
191    string getMinKey() {
192        if (sentinel->next == sentinel) {
193            return "";
194        }
195        return *(sentinel->next->keys.begin());
196    }
197};
198
199/**
200 * Your AllOne object will be instantiated and called as such:
201 * AllOne* obj = new AllOne();
202 * obj->inc(key);
203 * obj->dec(key);
204 * string param_3 = obj->getMaxKey();
205 * string param_4 = obj->getMinKey();
206 */
207
1/**
2 * Node class representing a bucket in the doubly-linked list
3 * Each node contains all strings with the same count value
4 */
5class Node {
6    prev: Node | null = null;
7    next: Node | null = null;
8    count: number;
9    keys: Set<string>;
10
11    constructor(key: string = "", count: number = 0) {
12        this.count = count;
13        this.keys = new Set<string>();
14        if (key !== "") {
15            this.keys.add(key);
16        }
17    }
18
19    /**
20     * Inserts a new node immediately after this node in the linked list
21     */
22    insertAfter(nodeToInsert: Node): Node {
23        nodeToInsert.prev = this;
24        nodeToInsert.next = this.next;
25        if (this.next) {
26            this.next.prev = nodeToInsert;
27        }
28        this.next = nodeToInsert;
29        return nodeToInsert;
30    }
31
32    /**
33     * Removes this node from the doubly-linked list
34     */
35    removeFromList(): void {
36        if (this.prev) {
37            this.prev.next = this.next;
38        }
39        if (this.next) {
40            this.next.prev = this.prev;
41        }
42    }
43}
44
45// Sentinel node for the doubly-linked list (acts as both head and tail marker)
46let sentinel: Node;
47
48// Maps each string key to its corresponding bucket node
49let keyToNodeMap: Map<string, Node>;
50
51/**
52 * Initializes the data structure with an empty sentinel node
53 */
54function AllOne(): void {
55    sentinel = new Node();
56    sentinel.next = sentinel;
57    sentinel.prev = sentinel;
58    keyToNodeMap = new Map<string, Node>();
59}
60
61/**
62 * Increments the count of the given key by 1
63 * If key doesn't exist, initializes it with count 1
64 */
65function inc(key: string): void {
66    if (!keyToNodeMap.has(key)) {
67        // Key doesn't exist - add it with count 1
68        if (sentinel.next === sentinel || sentinel.next!.count > 1) {
69            // Need to create a new node with count 1
70            const newNode = new Node(key, 1);
71            keyToNodeMap.set(key, sentinel.insertAfter(newNode));
72        } else {
73            // A node with count 1 already exists
74            sentinel.next!.keys.add(key);
75            keyToNodeMap.set(key, sentinel.next!);
76        }
77    } else {
78        // Key exists - increment its count
79        const currentNode = keyToNodeMap.get(key)!;
80        const nextNode = currentNode.next!;
81        const newCount = currentNode.count + 1;
82      
83        if (nextNode === sentinel || nextNode.count > newCount) {
84            // Need to create a new node with the incremented count
85            const newNode = new Node(key, newCount);
86            keyToNodeMap.set(key, currentNode.insertAfter(newNode));
87        } else {
88            // A node with the target count already exists
89            nextNode.keys.add(key);
90            keyToNodeMap.set(key, nextNode);
91        }
92      
93        // Remove key from current node and clean up if empty
94        currentNode.keys.delete(key);
95        if (currentNode.keys.size === 0) {
96            currentNode.removeFromList();
97        }
98    }
99}
100
101/**
102 * Decrements the count of the given key by 1
103 * If count reaches 0, removes the key entirely
104 * Assumes the key exists in the data structure
105 */
106function dec(key: string): void {
107    const currentNode = keyToNodeMap.get(key)!;
108  
109    if (currentNode.count === 1) {
110        // Count becomes 0 - remove the key entirely
111        keyToNodeMap.delete(key);
112    } else {
113        // Decrement the count
114        const previousNode = currentNode.prev!;
115        const newCount = currentNode.count - 1;
116      
117        if (previousNode === sentinel || previousNode.count < newCount) {
118            // Need to create a new node with the decremented count
119            const newNode = new Node(key, newCount);
120            keyToNodeMap.set(key, previousNode.insertAfter(newNode));
121        } else {
122            // A node with the target count already exists
123            previousNode.keys.add(key);
124            keyToNodeMap.set(key, previousNode);
125        }
126    }
127  
128    // Remove key from current node and clean up if empty
129    currentNode.keys.delete(key);
130    if (currentNode.keys.size === 0) {
131        currentNode.removeFromList();
132    }
133}
134
135/**
136 * Returns one of the keys with the maximum count
137 * Returns empty string if the data structure is empty
138 */
139function getMaxKey(): string {
140    if (sentinel.prev === sentinel) {
141        return "";
142    }
143    return sentinel.prev!.keys.values().next().value;
144}
145
146/**
147 * Returns one of the keys with the minimum count
148 * Returns empty string if the data structure is empty
149 */
150function getMinKey(): string {
151    if (sentinel.next === sentinel) {
152        return "";
153    }
154    return sentinel.next!.keys.values().next().value;
155}
156
157/**
158 * Your AllOne object will be instantiated and called as such:
159 * AllOne();
160 * inc(key);
161 * dec(key);
162 * const param_3 = getMaxKey();
163 * const param_4 = getMinKey();
164 */
165

Time and Space Complexity

Time Complexity:

  • inc(key): O(1) - The operation involves hash table lookups (O(1)), set operations (add and discard are O(1)), and doubly linked list insertion/removal (O(1)). All operations are constant time.
  • dec(key): O(1) - Similar to inc, this involves hash table lookups, set operations, and doubly linked list manipulation, all of which are constant time operations.
  • getMaxKey(): O(1) - Directly accesses the last node in the doubly linked list (self.root.prev) and retrieves an arbitrary key from its set using next(iter()), which is O(1).
  • getMinKey(): O(1) - Directly accesses the first node in the doubly linked list (self.root.next) and retrieves an arbitrary key from its set using next(iter()), which is O(1).

Space Complexity:

  • O(n) where n is the number of unique keys in the data structure.
  • The nodes dictionary stores n key-node mappings.
  • The doubly linked list contains at most n nodes (one for each unique count value, which is bounded by the number of keys).
  • Each node stores a set of keys with the same count, and the total number of keys across all sets is n.
  • Therefore, the overall space complexity is O(n).

Common Pitfalls

1. Incorrectly Handling Node Insertion Order

A critical pitfall is inserting new nodes in the wrong position when incrementing or decrementing counts. The doubly-linked list must maintain strict ordering where nodes are sorted by count value (ascending from root.next to root.prev).

Pitfall Example:

# WRONG: Inserting after the wrong node
if next_node == self.root or next_node.count > new_count:
    new_node = Node(key, new_count)
    # Bug: inserting after next_node instead of current_node
    self.key_to_node[key] = next_node.insert_after(new_node)

Solution: Always insert the new node immediately after the current node when incrementing, or after the previous node when decrementing:

# CORRECT: Insert after current_node when incrementing
if next_node == self.root or next_node.count > new_count:
    new_node = Node(key, new_count)
    self.key_to_node[key] = current_node.insert_after(new_node)

2. Forgetting to Update the key_to_node Mapping

When moving a key to a different node, failing to update the key_to_node dictionary will cause subsequent operations on that key to reference the wrong node.

Pitfall Example:

# WRONG: Not updating the mapping
if next_node.count == new_count:
    next_node.keys.add(key)
    # Bug: forgot to update key_to_node[key]

Solution: Always update the mapping whenever a key moves to a different node:

# CORRECT: Update the mapping
if next_node.count == new_count:
    next_node.keys.add(key)
    self.key_to_node[key] = next_node  # Essential update

3. Memory Leak from Empty Nodes

Not removing empty nodes from the linked list causes a memory leak and breaks the invariant that each node should contain at least one key.

Pitfall Example:

# WRONG: Not removing empty nodes
current_node.keys.discard(key)
# Bug: forgot to check if node is now empty

Solution: Always check and remove nodes that become empty after removing a key:

# CORRECT: Remove empty nodes
current_node.keys.discard(key)
if not current_node.keys:
    current_node.remove()

4. Edge Case in dec() When Count Becomes Zero

A subtle pitfall is not properly handling the case when decrementing a key with count 1. The key should be completely removed from the data structure, not moved to a "count 0" node.

Pitfall Example:

# WRONG: Trying to create a node with count 0
def dec(self, key: str) -> None:
    current_node = self.key_to_node[key]
    new_count = current_node.count - 1  # Could be 0!
    # Bug: might create a node with count 0
    new_node = Node(key, new_count)

Solution: Handle count 1 as a special case:

# CORRECT: Remove key entirely when count becomes 0
def dec(self, key: str) -> None:
    current_node = self.key_to_node[key]
  
    if current_node.count == 1:
        # Remove the key entirely
        del self.key_to_node[key]
    else:
        # Normal decrement logic
        new_count = current_node.count - 1
        # ... rest of the logic

5. Race Condition in getMinKey/getMaxKey with Empty Structure

Attempting to access root.next.keys or root.prev.keys when the structure is empty (root points to itself) will cause an error since root's keys set is empty.

Pitfall Example:

# WRONG: Accessing keys without checking if structure is empty
def getMinKey(self) -> str:
    # Bug: root.next might be root itself (empty structure)
    return next(iter(self.root.next.keys))

Solution: Always check if the structure is empty first:

# CORRECT: Check for empty structure
def getMinKey(self) -> str:
    if self.root.next == self.root:
        return ""
    return next(iter(self.root.next.keys))
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

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

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

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 assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More