Problem editorial

All O`one Data Structure

HardDesign PatternsHash TableLinked ListDesign

Editorial

Core insight

All O`one Data Structure · Design Patterns

Core Insight for All O`one Data Structure

The core insight needed to solve LeetCode 432 is recognizing that keys with the same count are equivalent for the purposes of getMaxKey and getMinKey. We do not need to order keys individually; we only need to order the counts.

Since inc and dec change a key's count by exactly 1, a key's "rank" changes incrementally. It moves from a bucket of count $C$ to a bucket of count $C+1$ or $C-1$ .

To maintain $O(1)$ access to the minimum and maximum counts, we can maintain a sorted sequence of existing counts. A Doubly Linked List is ideal for this because:

We can insert and remove nodes (counts) in $O(1)$ time if we have a pointer to the location.
The head and tail of the list provide immediate access to the Minimum and Maximum counts.

We combine this list with a Hash Map that maps every key to the specific Node in the linked list where that key currently resides. This allows us to jump directly to a key's current position in $O(1)$ time to update it.

Visual Description: Imagine a horizontal chain of buckets. Each bucket represents a number (the count). Inside each bucket is a set of strings that share that count.

The bucket on the far left (after the head) holds strings with the minimum count.
The bucket on the far right (before the tail) holds strings with the maximum count.
When we increment a key "A" currently in bucket 5, we remove "A" from bucket 5. We look at the next bucket. If it is bucket 6, we put "A" there. If the next bucket is 7 (or doesn't exist), we create a new bucket 6, insert it, and put "A" in it.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 432: All O`one Data Structure Solution & Explanation

Problem Overview

TL;DR: To achieve $O(1)$ time complexity for all operations, we combine a Hash Map with a Doubly Linked List where each node represents a specific frequency count and holds all keys with that count.

The LeetCode 432 problem asks us to design a data structure that tracks the frequency of strings. We must support incrementing a string's count, decrementing it, and retrieving the string with the minimum or maximum count. The critical constraint is that all operations, including finding the minimum and maximum, must run in $O(1)$ average time complexity.

This makes the All O`one Data Structure significantly more complex than a standard frequency map, as a standard map requires $O(N)$ time to scan for minimum or maximum values.

Brute Force Approach for All O`one Data Structure

A naive approach would be to use a standard Hash Map (HashMap<String, Integer>) to store the counts of each string.

Naive Logic

inc(key): Check if the key exists. If yes, increment value. If no, set value to 1.
dec(key): Decrement value. If value becomes 0, remove the key.
getMaxKey(): Iterate through all entries in the Hash Map, tracking the key with the highest value.
getMinKey(): Iterate through all entries in the Hash Map, tracking the key with the lowest value.

python

1# Pseudo-code for Brute Force
2class AllOneNaive:
3    def __init__(self):
4        self.counts = {}
5
6    def inc(self, key):
7        self.counts[key] = self.counts.get(key, 0) + 1
8
9    def getMaxKey(self):
10        if not self.counts: return ""
11        # Loop through all keys - O(N)
12        return max(self.counts, key=self.counts.get)

Why it Fails

While inc and dec are efficient ( $O(1)$ ), the getMaxKey and getMinKey operations are $O(N)$ , where $N$ is the number of unique keys. Given the constraint of $5 \times 10^4$ calls, if many calls are getMaxKey, the total runtime complexity approaches $O(N^2)$ , resulting in a Time Limit Exceeded (TLE) error. The problem strictly requires $O(1)$ .

Algorithm Strategy: Design Patterns

We will design a custom Doubly Linked List (DLL) where each Node contains:

count: An integer representing the frequency.
keys: A Set of strings having this frequency.
prev and next: Pointers to adjacent nodes.

We also maintain a global map: key -> Node.

Structure Maintenance

Doubly Linked List: Maintains the order of counts. head.next is always the node with the smallest count. tail.prev is always the node with the largest count.
Hash Map: Allows us to find which node a string belongs to in $O(1)$ time.

Handling Updates

When inc(key) is called:

Look up the current node of key in the map.
If it doesn't exist, we treat it as moving from count 0 to count 1. We insert key into the node with count=1 (creating it after head if necessary).
If it exists at node Current, we want to move it to a node with count = Current.count + 1. We check Current.next.
- If Current.next has the correct count, add key there.
- Otherwise, create a new node with the correct count, insert it after Current, and add key.
Remove key from Current. If Current becomes empty, remove Current from the list to keep the list size proportional to unique counts.

When dec(key) is called:

Look up the current node of key.
If Current.count > 1, we move key to a node with count - 1. Check Current.prev.
- If Current.prev has the correct count, add key.
- Otherwise, create a new node, insert it before Current, and add key.
If Current.count == 1, we simply remove the key from the data structure entirely.
Remove key from Current. If Current is empty, remove it from the list.

Execution Flow

Let's trace inc("a"), inc("b"), inc("a"), dec("b").

Initialize: head <-> tail. Map is empty.
inc("a"):
- "a" not in map.
- Check head.next. It is tail (count 0/dummy).
- Create Node N1 (count=1, keys={"a"}). Insert after head.
- Map: {"a": N1}. List: head <-> N1 <-> tail.
inc("b"):
- "b" not in map.
- Check head.next (N1). N1.count is 1.
- Add "b" to N1.
- Map: {"a": N1, "b": N1}. List: head <-> N1({"a","b"}) <-> tail.
inc("a"):
- "a" is in N1. Target count is 2.
- Check N1.next. It is tail.
- Create Node N2 (count=2). Insert after N1.
- Add "a" to N2. Remove "a" from N1. Update Map {"a": N2}.
- Map: {"a": N2, "b": N1}. List: head <-> N1({"b"}) <-> N2({"a"}) <-> tail.
dec("b"):
- "b" is in N1 (count 1).
- Target is count 0 (removal).
- Remove "b" from N1. Remove "b" from Map.
- N1 is now empty. Remove N1 from list.
- List: head <-> N2({"a"}) <-> tail.

Proof of Correctness

The algorithm relies on the invariant that the Doubly Linked List is strictly sorted by count.

Ordering: We only ever increment or decrement by 1. When incrementing from count $C$ , we look specifically for $C+1$ immediately to the right. If it's not there, we create it. This guarantees the list remains sorted ( $1, 2, 5, 6...$ ).
Min/Max: Because the list is sorted, head.next always holds the minimum non-zero count, and tail.prev always holds the maximum count. If the list is empty (only head/tail), no keys exist.
Efficiency: Map lookups are $O(1)$ . Linked List insertions/deletions at a known location are $O(1)$ . Therefore, all API calls are $O(1)$ .

Pattern Reuse Notes

The Design (Map + Doubly Linked List) pattern is a powerful combination for $O(1)$ constraint problems.

LeetCode 146: LRU Cache: Uses a Map for access and a DLL to track usage order.
LeetCode 155: Min Stack: Uses an auxiliary stack (conceptually similar to tracking metadata) to retrieve minimums in $O(1)$ .
LeetCode 225: Implement Stack using Queues: Involves structural design constraints.
LeetCode 232: Implement Queue using Stacks: Involves structural design constraints.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 432

cpp

1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <string>
5
6using namespace std;
7
8class AllOne {
9private:
10    struct Node {
11        int count;
12        unordered_set<string> keys;
13        Node *prev, *next;
14        Node(int c) : count(c), prev(nullptr), next(nullptr) {}
15    };
16
17    unordered_map<string, Node*> keyNodeMap;
18    Node *head, *tail;
19
20    // Helper to add a new node after a specific node
21    Node* addNodeAfter(Node* prevNode, int count) {
22        Node* newNode = new Node(count);
23        newNode->next = prevNode->next;
24        newNode->prev = prevNode;
25        prevNode->next->prev = newNode;
26        prevNode->next = newNode;
27        return newNode;
28    }
29
30    // Helper to remove a node from the list
31    void removeNode(Node* node) {
32        node->prev->next = node->next;
33        node->next->prev = node->prev;
34        delete node;
35    }
36
37public:
38    AllOne() {
39        head = new Node(0); // Sentinel head
40        tail = new Node(0); // Sentinel tail
41        head->next = tail;
42        tail->prev = head;
43    }
44
45    void inc(string key) {
46        if (keyNodeMap.find(key) == keyNodeMap.end()) {
47            // Key is new, add to bucket with count 1
48            if (head->next == tail || head->next->count != 1) {
49                addNodeAfter(head, 1);
50            }
51            head->next->keys.insert(key);
52            keyNodeMap[key] = head->next;
53        } else {
54            // Key exists, move to next bucket
55            Node* cur = keyNodeMap[key];
56            int nextCount = cur->count + 1;
57            if (cur->next == tail || cur->next->count != nextCount) {
58                addNodeAfter(cur, nextCount);
59            }
60            cur->next->keys.insert(key);
61            keyNodeMap[key] = cur->next;
62            
63            // Remove from current bucket
64            cur->keys.erase(key);
65            if (cur->keys.empty()) {
66                removeNode(cur);
67            }
68        }
69    }
70
71    void dec(string key) {
72        if (keyNodeMap.find(key) == keyNodeMap.end()) return;
73
74        Node* cur = keyNodeMap[key];
75        if (cur->count == 1) {
76            // Remove from data structure
77            keyNodeMap.erase(key);
78            cur->keys.erase(key);
79            if (cur->keys.empty()) removeNode(cur);
80        } else {
81            // Move to previous bucket
82            int prevCount = cur->count - 1;
83            if (cur->prev == head || cur->prev->count != prevCount) {
84                addNodeAfter(cur->prev, prevCount);
85            }
86            cur->prev->keys.insert(key);
87            keyNodeMap[key] = cur->prev;
88
89            // Remove from current bucket
90            cur->keys.erase(key);
91            if (cur->keys.empty()) removeNode(cur);
92        }
93    }
94
95    string getMaxKey() {
96        return (tail->prev == head) ? "" : *(tail->prev->keys.begin());
97    }
98
99    string getMinKey() {
100        return (head->next == tail) ? "" : *(head->next->keys.begin());
101    }
102};

Java Solution for LeetCode 432

java

1import java.util.*;
2
3class AllOne {
4    
5    private class Node {
6        int count;
7        Set<String> keys;
8        Node prev, next;
9        
10        Node(int count) {
11            this.count = count;
12            this.keys = new HashSet<>();
13        }
14    }
15    
16    private Map<String, Node> keyNodeMap;
17    private Node head, tail;
18
19    public AllOne() {
20        keyNodeMap = new HashMap<>();
21        head = new Node(0);
22        tail = new Node(0);
23        head.next = tail;
24        tail.prev = head;
25    }
26    
27    // Insert newNode after prevNode
28    private void insertAfter(Node prevNode, Node newNode) {
29        newNode.next = prevNode.next;
30        newNode.prev = prevNode;
31        prevNode.next.prev = newNode;
32        prevNode.next = newNode;
33    }
34    
35    // Remove node from DLL
36    private void removeNode(Node node) {
37        node.prev.next = node.next;
38        node.next.prev = node.prev;
39    }
40    
41    public void inc(String key) {
42        if (!keyNodeMap.containsKey(key)) {
43            // Key is new. Insert into bucket 1.
44            if (head.next == tail || head.next.count != 1) {
45                insertAfter(head, new Node(1));
46            }
47            head.next.keys.add(key);
48            keyNodeMap.put(key, head.next);
49        } else {
50            Node cur = keyNodeMap.get(key);
51            int nextCount = cur.count + 1;
52            
53            // Ensure next bucket exists
54            if (cur.next == tail || cur.next.count != nextCount) {
55                insertAfter(cur, new Node(nextCount));
56            }
57            
58            // Move key
59            cur.next.keys.add(key);
60            keyNodeMap.put(key, cur.next);
61            cur.keys.remove(key);
62            
63            if (cur.keys.isEmpty()) removeNode(cur);
64        }
65    }
66    
67    public void dec(String key) {
68        if (!keyNodeMap.containsKey(key)) return;
69        
70        Node cur = keyNodeMap.get(key);
71        if (cur.count == 1) {
72            keyNodeMap.remove(key);
73            cur.keys.remove(key);
74            if (cur.keys.isEmpty()) removeNode(cur);
75        } else {
76            int prevCount = cur.count - 1;
77            
78            // Ensure prev bucket exists
79            if (cur.prev == head || cur.prev.count != prevCount) {
80                insertAfter(cur.prev, new Node(prevCount));
81            }
82            
83            // Move key
84            cur.prev.keys.add(key);
85            keyNodeMap.put(key, cur.prev);
86            cur.keys.remove(key);
87            
88            if (cur.keys.isEmpty()) removeNode(cur);
89        }
90    }
91    
92    public String getMaxKey() {
93        return (tail.prev == head) ? "" : tail.prev.keys.iterator().next();
94    }
95    
96    public String getMinKey() {
97        return (head.next == tail) ? "" : head.next.keys.iterator().next();
98    }
99}

Python Solution for LeetCode 432

python

1class Node:
2    def __init__(self, count):
3        self.count = count
4        self.keys = set()
5        self.prev = None
6        self.next = None
7
8class AllOne:
9    def __init__(self):
10        self.key_node_map = {}
11        # Sentinel nodes
12        self.head = Node(0)
13        self.tail = Node(0)
14        self.head.next = self.tail
15        self.tail.prev = self.head
16
17    def _insert_after(self, prev_node, new_node):
18        new_node.next = prev_node.next
19        new_node.prev = prev_node
20        prev_node.next.prev = new_node
21        prev_node.next = new_node
22
23    def _remove_node(self, node):
24        node.prev.next = node.next
25        node.next.prev = node.prev
26
27    def inc(self, key: str) -> None:
28        if key not in self.key_node_map:
29            # Insert into bucket 1
30            if self.head.next == self.tail or self.head.next.count != 1:
31                self._insert_after(self.head, Node(1))
32            self.head.next.keys.add(key)
33            self.key_node_map[key] = self.head.next
34        else:
35            cur = self.key_node_map[key]
36            next_count = cur.count + 1
37            # Ensure next bucket exists
38            if cur.next == self.tail or cur.next.count != next_count:
39                self._insert_after(cur, Node(next_count))
40            
41            cur.next.keys.add(key)
42            self.key_node_map[key] = cur.next
43            cur.keys.remove(key)
44            
45            if not cur.keys:
46                self._remove_node(cur)
47
48    def dec(self, key: str) -> None:
49        if key not in self.key_node_map:
50            return
51        
52        cur = self.key_node_map[key]
53        if cur.count == 1:
54            self.key_node_map.pop(key)
55            cur.keys.remove(key)
56            if not cur.keys:
57                self._remove_node(cur)
58        else:
59            prev_count = cur.count - 1
60            # Ensure prev bucket exists
61            if cur.prev == self.head or cur.prev.count != prev_count:
62                self._insert_after(cur.prev, Node(prev_count))
63            
64            cur.prev.keys.add(key)
65            self.key_node_map[key] = cur.prev
66            cur.keys.remove(key)
67            
68            if not cur.keys:
69                self._remove_node(cur)
70
71    def getMaxKey(self) -> str:
72        if self.tail.prev == self.head:
73            return ""
74        # Return any element from the set
75        return next(iter(self.tail.prev.keys))
76
77    def getMinKey(self) -> str:
78        if self.head.next == self.tail:
79            return ""
80        return next(iter(self.head.next.keys))

AI Coach Insight

For All O`one Data Structure, focus on explaining why the structure works, not just naming Design Patterns.

Complexity Analysis

Time Complexity: $O(1)$ for inc, dec, getMaxKey, and getMinKey.
- Hash Map operations (get/put/remove) are $O(1)$ average.
- Doubly Linked List operations (insert/remove node) are $O(1)$ given pointers.
- Adding/removing from the HashSet inside the node is $O(1)$ .
Space Complexity: $O(N)$ , where $N$ $N$ is the number of stored keys.
- We store every key exactly once in the Map and exactly once in one Node's Set.
- The number of Nodes in the list is at most $N$ (worst case: every key has a different count).

Related Patterns

Pattern: Design Patterns
Subpattern: Design (General/Specific)

This problem fits the Design Pattern category because it requires composing multiple standard data structures (Hash Maps and Linked Lists) to satisfy strict time complexity constraints that neither can satisfy alone. Specifically, it utilizes a custom variation of the "Frequency List" design often seen in cache algorithms like LFU (Least Frequently Used).

Common Mistakes & FAQ

Q: Why does the Naive HashMap solution TLE?

Mistake: Using a simple HashMap<String, Integer> and iterating to find min/max. Concept Gap: Failure to recognize that iteration is $O(N)$ . With $5 \times 10^4$ operations, an $O(N)$ lookup leads to $O(N^2)$ overall, which is too slow. Consequence: Time Limit Exceeded.

Q: Why not use a Priority Queue?

Mistake: Using a Min-Heap and Max-Heap to track counts. Concept Gap: While Heaps give $O(1)$ access to the top element, updating an element inside a heap (incrementing its count) takes $O(\log N)$ to re-heapify. The problem strictly requires $O(1)$ . Consequence: Suboptimal time complexity ( $O(\log N)$ instead of $O(1)$ ).

Q: Why do we need to remove empty nodes?

Mistake: Leaving nodes in the Doubly Linked List when their keys set becomes empty. Concept Gap: If empty nodes remain, getMinKey might look at head.next and find an empty bucket, forcing it to traverse further (breaking $O(1)$ ) or return an incorrect empty string. Consequence: Correctness failure or performance degradation.

Q: Can't we just use `TreeMap` (Java) or `SortedDict`?

Mistake: Using a tree-based map to keep keys sorted by count. Concept Gap: Tree-based structures operate in $O(\log N)$ time for insertion and deletion. This violates the strict $O(1)$ requirement. Consequence: Suboptimal time complexity.

Practise All O`one Data Structure and the problems around it

All O`one Data Structure is a Design Patterns problem, in the Design (General/Specific) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

All O`one Data Structure · Design Patterns

Core Insight for All O`one Data Structure

Since inc and dec change a key's count by exactly 1, a key's "rank" changes incrementally. It moves from a bucket of count $C$ to a bucket of count $C+1$ or $C-1$ .

To maintain $O(1)$ access to the minimum and maximum counts, we can maintain a sorted sequence of existing counts. A Doubly Linked List is ideal for this because:

We can insert and remove nodes (counts) in $O(1)$ time if we have a pointer to the location.
The head and tail of the list provide immediate access to the Minimum and Maximum counts.

Visual Description: Imagine a horizontal chain of buckets. Each bucket represents a number (the count). Inside each bucket is a set of strings that share that count.

The bucket on the far left (after the head) holds strings with the minimum count.
The bucket on the far right (before the tail) holds strings with the maximum count.
When we increment a key "A" currently in bucket 5, we remove "A" from bucket 5. We look at the next bucket. If it is bucket 6, we put "A" there. If the next bucket is 7 (or doesn't exist), we create a new bucket 6, insert it, and put "A" in it.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 432: All O`one Data Structure Solution & Explanation

Problem Overview

This makes the All O`one Data Structure significantly more complex than a standard frequency map, as a standard map requires $O(N)$ time to scan for minimum or maximum values.

Brute Force Approach for All O`one Data Structure

A naive approach would be to use a standard Hash Map (HashMap<String, Integer>) to store the counts of each string.

Naive Logic

inc(key): Check if the key exists. If yes, increment value. If no, set value to 1.
dec(key): Decrement value. If value becomes 0, remove the key.
getMaxKey(): Iterate through all entries in the Hash Map, tracking the key with the highest value.
getMinKey(): Iterate through all entries in the Hash Map, tracking the key with the lowest value.

python

1# Pseudo-code for Brute Force
2class AllOneNaive:
3    def __init__(self):
4        self.counts = {}
5
6    def inc(self, key):
7        self.counts[key] = self.counts.get(key, 0) + 1
8
9    def getMaxKey(self):
10        if not self.counts: return ""
11        # Loop through all keys - O(N)
12        return max(self.counts, key=self.counts.get)

Why it Fails

Algorithm Strategy: Design Patterns

We will design a custom Doubly Linked List (DLL) where each Node contains:

count: An integer representing the frequency.
keys: A Set of strings having this frequency.
prev and next: Pointers to adjacent nodes.

We also maintain a global map: key -> Node.

Structure Maintenance

Doubly Linked List: Maintains the order of counts. head.next is always the node with the smallest count. tail.prev is always the node with the largest count.
Hash Map: Allows us to find which node a string belongs to in $O(1)$ time.

Handling Updates

When inc(key) is called:

Look up the current node of key in the map.
If it doesn't exist, we treat it as moving from count 0 to count 1. We insert key into the node with count=1 (creating it after head if necessary).
If it exists at node Current, we want to move it to a node with count = Current.count + 1. We check Current.next.
- If Current.next has the correct count, add key there.
- Otherwise, create a new node with the correct count, insert it after Current, and add key.
Remove key from Current. If Current becomes empty, remove Current from the list to keep the list size proportional to unique counts.

When dec(key) is called:

Look up the current node of key.
If Current.count > 1, we move key to a node with count - 1. Check Current.prev.
- If Current.prev has the correct count, add key.
- Otherwise, create a new node, insert it before Current, and add key.
If Current.count == 1, we simply remove the key from the data structure entirely.
Remove key from Current. If Current is empty, remove it from the list.

Execution Flow

Let's trace inc("a"), inc("b"), inc("a"), dec("b").

Initialize: head <-> tail. Map is empty.
inc("a"):
- "a" not in map.
- Check head.next. It is tail (count 0/dummy).
- Create Node N1 (count=1, keys={"a"}). Insert after head.
- Map: {"a": N1}. List: head <-> N1 <-> tail.
inc("b"):
- "b" not in map.
- Check head.next (N1). N1.count is 1.
- Add "b" to N1.
- Map: {"a": N1, "b": N1}. List: head <-> N1({"a","b"}) <-> tail.
inc("a"):
- "a" is in N1. Target count is 2.
- Check N1.next. It is tail.
- Create Node N2 (count=2). Insert after N1.
- Add "a" to N2. Remove "a" from N1. Update Map {"a": N2}.
- Map: {"a": N2, "b": N1}. List: head <-> N1({"b"}) <-> N2({"a"}) <-> tail.
dec("b"):
- "b" is in N1 (count 1).
- Target is count 0 (removal).
- Remove "b" from N1. Remove "b" from Map.
- N1 is now empty. Remove N1 from list.
- List: head <-> N2({"a"}) <-> tail.

Proof of Correctness

The algorithm relies on the invariant that the Doubly Linked List is strictly sorted by count.

Ordering: We only ever increment or decrement by 1. When incrementing from count $C$ , we look specifically for $C+1$ immediately to the right. If it's not there, we create it. This guarantees the list remains sorted ( $1, 2, 5, 6...$ ).
Min/Max: Because the list is sorted, head.next always holds the minimum non-zero count, and tail.prev always holds the maximum count. If the list is empty (only head/tail), no keys exist.
Efficiency: Map lookups are $O(1)$ . Linked List insertions/deletions at a known location are $O(1)$ . Therefore, all API calls are $O(1)$ .

Pattern Reuse Notes

The Design (Map + Doubly Linked List) pattern is a powerful combination for $O(1)$ constraint problems.

LeetCode 146: LRU Cache: Uses a Map for access and a DLL to track usage order.
LeetCode 155: Min Stack: Uses an auxiliary stack (conceptually similar to tracking metadata) to retrieve minimums in $O(1)$ .
LeetCode 225: Implement Stack using Queues: Involves structural design constraints.
LeetCode 232: Implement Queue using Stacks: Involves structural design constraints.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 432

cpp

1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <string>
5
6using namespace std;
7
8class AllOne {
9private:
10    struct Node {
11        int count;
12        unordered_set<string> keys;
13        Node *prev, *next;
14        Node(int c) : count(c), prev(nullptr), next(nullptr) {}
15    };
16
17    unordered_map<string, Node*> keyNodeMap;
18    Node *head, *tail;
19
20    // Helper to add a new node after a specific node
21    Node* addNodeAfter(Node* prevNode, int count) {
22        Node* newNode = new Node(count);
23        newNode->next = prevNode->next;
24        newNode->prev = prevNode;
25        prevNode->next->prev = newNode;
26        prevNode->next = newNode;
27        return newNode;
28    }
29
30    // Helper to remove a node from the list
31    void removeNode(Node* node) {
32        node->prev->next = node->next;
33        node->next->prev = node->prev;
34        delete node;
35    }
36
37public:
38    AllOne() {
39        head = new Node(0); // Sentinel head
40        tail = new Node(0); // Sentinel tail
41        head->next = tail;
42        tail->prev = head;
43    }
44
45    void inc(string key) {
46        if (keyNodeMap.find(key) == keyNodeMap.end()) {
47            // Key is new, add to bucket with count 1
48            if (head->next == tail || head->next->count != 1) {
49                addNodeAfter(head, 1);
50            }
51            head->next->keys.insert(key);
52            keyNodeMap[key] = head->next;
53        } else {
54            // Key exists, move to next bucket
55            Node* cur = keyNodeMap[key];
56            int nextCount = cur->count + 1;
57            if (cur->next == tail || cur->next->count != nextCount) {
58                addNodeAfter(cur, nextCount);
59            }
60            cur->next->keys.insert(key);
61            keyNodeMap[key] = cur->next;
62            
63            // Remove from current bucket
64            cur->keys.erase(key);
65            if (cur->keys.empty()) {
66                removeNode(cur);
67            }
68        }
69    }
70
71    void dec(string key) {
72        if (keyNodeMap.find(key) == keyNodeMap.end()) return;
73
74        Node* cur = keyNodeMap[key];
75        if (cur->count == 1) {
76            // Remove from data structure
77            keyNodeMap.erase(key);
78            cur->keys.erase(key);
79            if (cur->keys.empty()) removeNode(cur);
80        } else {
81            // Move to previous bucket
82            int prevCount = cur->count - 1;
83            if (cur->prev == head || cur->prev->count != prevCount) {
84                addNodeAfter(cur->prev, prevCount);
85            }
86            cur->prev->keys.insert(key);
87            keyNodeMap[key] = cur->prev;
88
89            // Remove from current bucket
90            cur->keys.erase(key);
91            if (cur->keys.empty()) removeNode(cur);
92        }
93    }
94
95    string getMaxKey() {
96        return (tail->prev == head) ? "" : *(tail->prev->keys.begin());
97    }
98
99    string getMinKey() {
100        return (head->next == tail) ? "" : *(head->next->keys.begin());
101    }
102};

Java Solution for LeetCode 432

java

1import java.util.*;
2
3class AllOne {
4    
5    private class Node {
6        int count;
7        Set<String> keys;
8        Node prev, next;
9        
10        Node(int count) {
11            this.count = count;
12            this.keys = new HashSet<>();
13        }
14    }
15    
16    private Map<String, Node> keyNodeMap;
17    private Node head, tail;
18
19    public AllOne() {
20        keyNodeMap = new HashMap<>();
21        head = new Node(0);
22        tail = new Node(0);
23        head.next = tail;
24        tail.prev = head;
25    }
26    
27    // Insert newNode after prevNode
28    private void insertAfter(Node prevNode, Node newNode) {
29        newNode.next = prevNode.next;
30        newNode.prev = prevNode;
31        prevNode.next.prev = newNode;
32        prevNode.next = newNode;
33    }
34    
35    // Remove node from DLL
36    private void removeNode(Node node) {
37        node.prev.next = node.next;
38        node.next.prev = node.prev;
39    }
40    
41    public void inc(String key) {
42        if (!keyNodeMap.containsKey(key)) {
43            // Key is new. Insert into bucket 1.
44            if (head.next == tail || head.next.count != 1) {
45                insertAfter(head, new Node(1));
46            }
47            head.next.keys.add(key);
48            keyNodeMap.put(key, head.next);
49        } else {
50            Node cur = keyNodeMap.get(key);
51            int nextCount = cur.count + 1;
52            
53            // Ensure next bucket exists
54            if (cur.next == tail || cur.next.count != nextCount) {
55                insertAfter(cur, new Node(nextCount));
56            }
57            
58            // Move key
59            cur.next.keys.add(key);
60            keyNodeMap.put(key, cur.next);
61            cur.keys.remove(key);
62            
63            if (cur.keys.isEmpty()) removeNode(cur);
64        }
65    }
66    
67    public void dec(String key) {
68        if (!keyNodeMap.containsKey(key)) return;
69        
70        Node cur = keyNodeMap.get(key);
71        if (cur.count == 1) {
72            keyNodeMap.remove(key);
73            cur.keys.remove(key);
74            if (cur.keys.isEmpty()) removeNode(cur);
75        } else {
76            int prevCount = cur.count - 1;
77            
78            // Ensure prev bucket exists
79            if (cur.prev == head || cur.prev.count != prevCount) {
80                insertAfter(cur.prev, new Node(prevCount));
81            }
82            
83            // Move key
84            cur.prev.keys.add(key);
85            keyNodeMap.put(key, cur.prev);
86            cur.keys.remove(key);
87            
88            if (cur.keys.isEmpty()) removeNode(cur);
89        }
90    }
91    
92    public String getMaxKey() {
93        return (tail.prev == head) ? "" : tail.prev.keys.iterator().next();
94    }
95    
96    public String getMinKey() {
97        return (head.next == tail) ? "" : head.next.keys.iterator().next();
98    }
99}

Python Solution for LeetCode 432

python

1class Node:
2    def __init__(self, count):
3        self.count = count
4        self.keys = set()
5        self.prev = None
6        self.next = None
7
8class AllOne:
9    def __init__(self):
10        self.key_node_map = {}
11        # Sentinel nodes
12        self.head = Node(0)
13        self.tail = Node(0)
14        self.head.next = self.tail
15        self.tail.prev = self.head
16
17    def _insert_after(self, prev_node, new_node):
18        new_node.next = prev_node.next
19        new_node.prev = prev_node
20        prev_node.next.prev = new_node
21        prev_node.next = new_node
22
23    def _remove_node(self, node):
24        node.prev.next = node.next
25        node.next.prev = node.prev
26
27    def inc(self, key: str) -> None:
28        if key not in self.key_node_map:
29            # Insert into bucket 1
30            if self.head.next == self.tail or self.head.next.count != 1:
31                self._insert_after(self.head, Node(1))
32            self.head.next.keys.add(key)
33            self.key_node_map[key] = self.head.next
34        else:
35            cur = self.key_node_map[key]
36            next_count = cur.count + 1
37            # Ensure next bucket exists
38            if cur.next == self.tail or cur.next.count != next_count:
39                self._insert_after(cur, Node(next_count))
40            
41            cur.next.keys.add(key)
42            self.key_node_map[key] = cur.next
43            cur.keys.remove(key)
44            
45            if not cur.keys:
46                self._remove_node(cur)
47
48    def dec(self, key: str) -> None:
49        if key not in self.key_node_map:
50            return
51        
52        cur = self.key_node_map[key]
53        if cur.count == 1:
54            self.key_node_map.pop(key)
55            cur.keys.remove(key)
56            if not cur.keys:
57                self._remove_node(cur)
58        else:
59            prev_count = cur.count - 1
60            # Ensure prev bucket exists
61            if cur.prev == self.head or cur.prev.count != prev_count:
62                self._insert_after(cur.prev, Node(prev_count))
63            
64            cur.prev.keys.add(key)
65            self.key_node_map[key] = cur.prev
66            cur.keys.remove(key)
67            
68            if not cur.keys:
69                self._remove_node(cur)
70
71    def getMaxKey(self) -> str:
72        if self.tail.prev == self.head:
73            return ""
74        # Return any element from the set
75        return next(iter(self.tail.prev.keys))
76
77    def getMinKey(self) -> str:
78        if self.head.next == self.tail:
79            return ""
80        return next(iter(self.head.next.keys))

Core Insight for All O`one Data Structure

LeetCode 432: All O`one Data Structure Solution & Explanation

Problem Overview

Brute Force Approach for All O`one Data Structure

Naive Logic

Why it Fails

Algorithm Strategy: Design Patterns

Structure Maintenance

Handling Updates

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 432

Java Solution for LeetCode 432

Python Solution for LeetCode 432

Practise All O`one Data Structure and the problems around it

Related problems

Core Insight for All O`one Data Structure

LeetCode 432: All O`one Data Structure Solution & Explanation

Problem Overview

Brute Force Approach for All O`one Data Structure

Naive Logic

Why it Fails

Algorithm Strategy: Design Patterns

Structure Maintenance

Handling Updates

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 432

Java Solution for LeetCode 432

Python Solution for LeetCode 432

Practise All O`one Data Structure and the problems around it

Related problems