Log inSign up
hardLeetCodeNot Started

All O(1) Data Structure

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Design a data structure to store 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 reaches 0, remove it from the data structure. It is guaranteed that key exists in the data structure before 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 minimal count. If no element exists, return an empty string "".

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

Example 1 · Example 1: Standard Lifecycle:

Input: inc("hello"), inc("hello"), getMaxKey(), getMinKey(), inc("leet"), getMaxKey(), getMinKey()
Output: ["hello", "hello", "hello", "leet"]
Explanation: - hello: count 2.\n- getMaxKey: "hello" (count 2), getMinKey: "hello" (count 2).\n- leet: count 1.\n- getMaxKey: "hello" (count 2), getMinKey: "leet" (count 1).

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why grouping by frequency enables constant-time operations.
  • Master doubly linked list manipulation with sentinel head and tail nodes.
  • Implement the complete All O(1) data structure across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Real-time min and max retrieval with continuous increment/decrement.
  • Strict O(1) requirement across all queries.
  • Key-frequency association.

Algorithmic Decision Tree:

  • If O(1) max/min + dynamic frequency updates required -> Bucketed Doubly Linked List + Hash Map.
  • If O(log N) is acceptable -> Treap / TreeMap / Priority Queue.

Connected Patterns:

LRU CacheLFU CacheDesign Underground System

1. Hash Map with Linear Extreme Scan

Intuition

Keep an unordered_map of string to integer count. inc increments the integer; dec decrements it (and removes it if 0). getMaxKey and getMinKey iterate across all entries in the map to find the key with maximum or minimum count.

When to apply: When total unique keys are small (K <= 50) and get queries are rare.

Algorithm

  1. Step 1: In inc(key), map[key]++.
  2. Step 2: In dec(key), decrement map[key]; if count is 0, delete key.
  3. Step 3: In getMaxKey, scan map finding key with max count.
  4. Step 4: In getMinKey, scan map finding key with min count.
  5. Step 5: Return empty string if map is empty.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5using namespace std;
6
7class AllOne {
8 unordered_map<string, int> counts;
9public:
10 AllOne() {}
11
12 void inc(string key) {
13 counts[key]++;
14 }
15
16 void dec(string key) {
17 counts[key]--;
18 if (counts[key] == 0) counts.erase(key);
19 }
20
21 string getMaxKey() {
22 if (counts.empty()) return "";
23 string maxKey = "";
24 int maxVal = -1;
25 for (const auto& [k, v] : counts) {
26 if (v > maxVal) {
27 maxVal = v;
28 maxKey = k;
29 }
30 }
31 return maxKey;
32 }
33
34 string getMinKey() {
35 if (counts.empty()) return "";
36 string minKey = "";
37 int minVal = 1e9;
38 for (const auto& [k, v] : counts) {
39 if (v < minVal) {
40 minVal = v;
41 minKey = k;
42 }
43 }
44 return minKey;
45 }
46};
47
48int main() {
49 AllOne allOne;
50 allOne.inc("hello");
51 allOne.inc("hello");
52 cout << "Max: " << allOne.getMaxKey() << endl; // hello
53 cout << "Min: " << allOne.getMinKey() << endl; // hello
54 allOne.inc("leet");
55 cout << "Max: " << allOne.getMaxKey() << endl; // hello
56 cout << "Min: " << allOne.getMinKey() << endl; // leet
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(1) inc/dec, O(K) getMaxKey/getMinKey
  • Space complexity: O(K)

2. Hash Map + Frequency Ordered Map (Tree)

Intuition

Use a map from key to frequency, plus a self-balancing BST mapping frequency to a set of keys. Finding min and max takes O(1) via the first and last keys in the BST, but incrementing or decrementing takes O(log K) to re-insert.

When to apply: When O(log K) per increment/decrement is permissible.

Algorithm

  1. Step 1: Map key to count.
  2. Step 2: Maintain BST of count to set of keys.
  3. Step 3: On inc/dec, remove key from old count set in BST, insert into new count set.
  4. Step 4: If a count set becomes empty, remove that count from the BST.
  5. Step 5: getMaxKey retrieves any key from the highest count in the BST.
  6. Step 6: getMinKey retrieves any key from the lowest count in the BST.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5#include <map>
6
7using namespace std;
8
9class AllOne {
10 unordered_map<string, int> keyCount;
11 map<int, unordered_set<string>> countKeys;
12public:
13 AllOne() {}
14
15 void inc(string key) {
16 int oldC = keyCount[key];
17 int newC = oldC + 1;
18 keyCount[key] = newC;
19
20 if (oldC > 0) {
21 countKeys[oldC].erase(key);
22 if (countKeys[oldC].empty()) countKeys.erase(oldC);
23 }
24 countKeys[newC].insert(key);
25 }
26
27 void dec(string key) {
28 int oldC = keyCount[key];
29 countKeys[oldC].erase(key);
30 if (countKeys[oldC].empty()) countKeys.erase(oldC);
31
32 if (oldC == 1) {
33 keyCount.erase(key);
34 } else {
35 int newC = oldC - 1;
36 keyCount[key] = newC;
37 countKeys[newC].insert(key);
38 }
39 }
40
41 string getMaxKey() {
42 if (countKeys.empty()) return "";
43 return *(countKeys.rbegin()->second.begin());
44 }
45
46 string getMinKey() {
47 if (countKeys.empty()) return "";
48 return *(countKeys.begin()->second.begin());
49 }
50};
51
52int main() {
53 AllOne allOne;
54 allOne.inc("hello");
55 allOne.inc("hello");
56 cout << "Max: " << allOne.getMaxKey() << endl;
57 cout << "Min: " << allOne.getMinKey() << endl;
58 allOne.inc("leet");
59 cout << "Max: " << allOne.getMaxKey() << endl;
60 cout << "Min: " << allOne.getMinKey() << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(log K) inc/dec, O(1) getMaxKey/getMinKey
  • Space complexity: O(K)

3. Hash Map + Doubly Linked List of Frequency Buckets

Intuition

Maintain a DLL where each node represents a frequency bucket Node(count) holding a set of keys. A hash map points each key to its corresponding bucket node. Because increment/decrement always changes frequency by exactly +/- 1, the new bucket node is either adjacent to the current node or can be created adjacent in O(1). Sentinel head and tail provide O(1) min and max retrieval.

When to apply: When all operations (insert, delete, getMin, getMax) must run in strict O(1) average time.

Algorithm

  1. Step 1: Create a DLL with dummy head and tail sentinel nodes.
  2. Step 2: Map each key to its Node in the DLL.
  3. Step 3: In inc(key): if key is new, add to bucket with count 1 (create after head if needed). If key exists, move from node with count C to adjacent node with count C + 1.
  4. Step 4: In dec(key): move from node with count C to adjacent node with count C - 1 (or remove if C = 1).
  5. Step 5: Remove empty bucket nodes from the DLL.
  6. Step 6: getMaxKey returns any key from tail.prev.keys; getMinKey returns any key from head.next.keys.

Interactive Trace for All O(1)

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: 'a' and 'b' incremented once
Visual state
Values and pointers at this exact step
pointers
S
{'a', 'b'}
0
↑ head.next↑ tail.prev
Check / comparison
Head points to Bucket 1, Tail points to Bucket 1.
Decision / next transition
Single bucket created at frequency 1.
Why this step matters

Step 1: a and b incremented once. Both reside in Bucket 1: head <-> [count:1, keys: {a, b}] <-> tail.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5
6using namespace std;
7
8struct Node {
9 int count;
10 unordered_set<string> keys;
11 Node *prev, *next;
12 Node(int c) : count(c), prev(nullptr), next(nullptr) {}
13};
14
15class AllOne {
16 Node *head, *tail;
17 unordered_map<string, Node*> keyNode;
18
19 Node* insertAfter(Node* prevNode, int count) {
20 Node* newNode = new Node(count);
21 newNode->next = prevNode->next;
22 newNode->prev = prevNode;
23 prevNode->next->prev = newNode;
24 prevNode->next = newNode;
25 return newNode;
26 }
27
28 void removeNode(Node* node) {
29 node->prev->next = node->next;
30 node->next->prev = node->prev;
31 delete node;
32 }
33
34public:
35 AllOne() {
36 head = new Node(0);
37 tail = new Node(0);
38 head->next = tail;
39 tail->prev = head;
40 }
41
42 void inc(string key) {
43 if (keyNode.find(key) == keyNode.end()) {
44 if (head->next == tail || head->next->count > 1) {
45 insertAfter(head, 1);
46 }
47 head->next->keys.insert(key);
48 keyNode[key] = head->next;
49 } else {
50 Node* cur = keyNode[key];
51 if (cur->next == tail || cur->next->count > cur->count + 1) {
52 insertAfter(cur, cur->count + 1);
53 }
54 cur->next->keys.insert(key);
55 keyNode[key] = cur->next;
56
57 cur->keys.erase(key);
58 if (cur->keys.empty()) removeNode(cur);
59 }
60 }
61
62 void dec(string key) {
63 Node* cur = keyNode[key];
64 if (cur->count == 1) {
65 keyNode.erase(key);
66 } else {
67 if (cur->prev == head || cur->prev->count < cur->count - 1) {
68 insertAfter(cur->prev, cur->count - 1);
69 }
70 cur->prev->keys.insert(key);
71 keyNode[key] = cur->prev;
72 }
73
74 cur->keys.erase(key);
75 if (cur->keys.empty()) removeNode(cur);
76 }
77
78 string getMaxKey() {
79 if (tail->prev == head) return "";
80 return *(tail->prev->keys.begin());
81 }
82
83 string getMinKey() {
84 if (head->next == tail) return "";
85 return *(head->next->keys.begin());
86 }
87};
88
89int main() {
90 AllOne allOne;
91 allOne.inc("hello");
92 allOne.inc("hello");
93 cout << "Max: " << allOne.getMaxKey() << endl; // hello
94 cout << "Min: " << allOne.getMinKey() << endl; // hello
95 allOne.inc("leet");
96 cout << "Max: " << allOne.getMaxKey() << endl; // hello
97 cout << "Min: " << allOne.getMinKey() << endl; // leet
98 return 0;
99}

Time & Space Complexity

  • Time complexity: O(1) strictly for all operations
  • Space complexity: O(K)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Simple Hash MapO(1) inc/dec, O(K) getMaxKey/getMinKeyO(K)Maintain an unordered map of key to count. For getMaxKey and getMinKey, iterate through all keys to find the extremes.Iterating through all keys for min/max queries.
2.Better — Hash Map + Balanced BST / Sorted MapO(log K) inc/dec, O(1) getMaxKey/getMinKeyO(K)Use a hash map for key-to-count, and a sorted map (or multiset/treap) of count-to-keys. Extremes are at the ends of the sorted map.Tree rebalancing overhead on frequency change.
3.Optimal — Hash Map + Doubly Linked List of Frequency BucketsOptimalO(1) strictly for all operationsO(K)Chain frequency buckets with a DLL. Map key -> bucket pointer. Moving between adjacent frequencies is pointer manipulation in O(1).DLL node splicing.

Common Pitfalls & Crucial Edge Cases

Creating a list node per key instead of per frequency bucket

Moving a single key between adjacent buckets takes O(1) only when keys share bucket nodes.

Failing to delete empty bucket nodes

If a bucket becomes empty and is not removed, head.next or tail.prev may point to empty buckets, returning empty string incorrectly.

Unordered set key extraction inefficiency

Using *bucket.keys.begin() provides O(1) key extraction without copying.

Crucial Edge Cases to Validate:

  • Calling getMaxKey / getMinKey when data structure is empty — Must return the empty string "".
  • Only one key present — Both getMaxKey and getMinKey return the same key.
  • Multiple keys sharing the same maximum or minimum frequency — Any of those keys is a valid answer.
  • Frequent increment and decrement causing empty buckets — Must unlink empty bucket nodes to prevent memory leaks and maintain O(1) head/tail access.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the dual-structure diagram: Hash Map (Key -> BucketNode) + Doubly Linked List of BucketNodes (each holding count and Set<Key>).
  2. Highlight the analogy to LFU Cache, which uses a very similar bucketed doubly linked list architecture.
  3. Emphasize sentinel head and tail dummy nodes to eliminate null checks during node insertion and deletion.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why cannot a standard balanced binary search tree or priority queue achieve O(1) for all operations in All O(1)?

2.How does the bucketed Doubly Linked List maintain O(1) for getMaxKey and getMinKey?

3.What happens when a key's count drops to 0 after dec()?

Back to DSA Sheet