Your Dashboard
Interview Coaching
Learn
System Design
ML System Design
Code
Behavioral
Salary Negotiation
Interview Guides
Leetcode 432. All O`one Data Structure
Asked at:
Meta
Atlassian
DESCRIPTION
Design a data structure that maintains string keys with integer counts and supports four operations in O(1) average time: inc(key) to increment a key's count, dec(key) to decrement (removing the key if count reaches zero), getMaxKey() to return any key with maximum count, and getMinKey() to return any key with minimum count. For example, after inc("a"), inc("b"), inc("a"), calling getMaxKey() should return "a" (count 2) and getMinKey() should return "b" (count 1).
Input:
Output:
Explanation: After two increments, "apple" has count 2 (max) and "banana" has count 1 (min). After decrementing "apple", both have count 1.
Constraints:
- All operations must run in O(1) average time complexity
- Keys are strings, counts are positive integers
- When count reaches 0, the key must be removed from the data structure
- getMaxKey() and getMinKey() return empty string if no keys exist
Understanding the Problem
The core challenge is maintaining both key-to-count mappings and count-to-keys groupings simultaneously while supporting O(1) operations. A naive approach using only a hash map requires O(n) time to find min/max counts. The solution requires a doubly-linked list of count buckets where each bucket stores all keys with that count, combined with hash maps for O(1) access to both keys and count nodes. The critical insight is that inc and dec operations only move keys between adjacent count buckets, enabling efficient list manipulation.
Building Intuition
A naive approach using a hash map {key: count} and scanning all values for min/max takes O(n) time. A better approach uses a doubly-linked list where each node represents a count level and contains a set of keys at that count, plus a hash map {key: countNode} for direct access. For example, after inc("a") twice and inc("b") once, the list looks like: [count=1: {"b"}] <-> [count=2: {"a"}], with head pointing to min and tail to max.
This pattern appears in real-time analytics systems (tracking trending items), LRU/LFU caches (eviction policies), and leaderboard systems where you need instant access to top/bottom performers. The ability to maintain sorted order without sorting is crucial for high-throughput systems where latency matters.
Common Pitfalls
Implementation
Data Structure Design and Initialization
The solution uses three core components: a keyCountMap hash map storing {key: countNode} for O(1) key lookup, a doubly-linked list of count buckets where each CountNode has a count value and a keys set, and head/tail pointers to the min/max count nodes. Each CountNode maintains prev and next pointers for efficient insertion/deletion. For example, the structure for keys "a" (count 2) and "b" (count 1) would be: head -> [count=1, keys={"b"}] <-> [count=2, keys={"a"}] <- tail.
class CountNode:def __init__(self, count):self.count = countself.keys = set()self.prev = Noneself.next = Noneclass AllOne:def __init__(self):self.keyCountMap = {}self.head = Noneself.tail = None
Increment Operation Implementation
The inc(key) operation first checks if the key exists in keyCountMap. If new, it finds or creates a count=1 bucket at the list head and adds the key. If existing, it removes the key from its current count bucket, finds or creates the count+1 bucket (always adjacent to current), and moves the key there. After moving, if the old bucket is empty, it's unlinked from the list. For example, inc("a") when "a" is at count 2 moves it from the count=2 bucket to count=3, creating the count=3 bucket if needed.
def inc(self, key: str) -> None:if key not in self.keyCountMap:if not self.head.next or self.head.next.count != 1:newBucket = Bucket(1)self._insertBucketAfter(self.head, newBucket)self.head.next.keys.add(key)self.keyCountMap[key] = self.head.nextelse:curBucket = self.keyCountMap[key]newCount = curBucket.count + 1if not curBucket.next or curBucket.next.count != newCount:newBucket = Bucket(newCount)self._insertBucketAfter(curBucket, newBucket)curBucket.keys.remove(key)curBucket.next.keys.add(key)self.keyCountMap[key] = curBucket.nextif not curBucket.keys:self._removeBucket(curBucket)
Decrement Operation Implementation
The dec(key) operation retrieves the key's current count node from keyCountMap and removes the key from that bucket's set. If the new count is 0, the key is removed from keyCountMap entirely. Otherwise, it finds or creates the count-1 bucket (adjacent to current) and adds the key there. Empty buckets are unlinked from the list. For example, dec("b") at count 1 removes "b" completely, while dec("a") at count 3 moves it to the count=2 bucket.
def dec(self, key: str) -> None:if key not in self.key_count_map:returnnode = self.key_count_map[key]node.keys.remove(key)if node.count == 1:del self.key_count_map[key]else:prev_node = node.previf prev_node == self.head or prev_node.count != node.count - 1:new_node = Node(node.count - 1)self._insert_after(prev_node, new_node)prev_node = new_nodeprev_node.keys.add(key)self.key_count_map[key] = prev_nodeif not node.keys:self._remove_node(node)
Min/Max Key Retrieval
The getMinKey() returns any key from head.keys (the first non-empty bucket), while getMaxKey() returns any key from tail.keys (the last non-empty bucket). Both operations are O(1) since head and tail pointers are maintained during all modifications. If the list is empty (no keys exist), both return an empty string. For example, with buckets [count=1: {"b"}] <-> [count=5: {"a", "c"}], getMinKey() returns "b" and getMaxKey() returns either "a" or "c".
def getMaxKey(self) -> str:"""Return any key with maximum count, or empty string if no keys exist."""if self.tail.prev == self.head:return ""return next(iter(self.tail.prev.keys))def getMinKey(self) -> str:"""Return any key with minimum count, or empty string if no keys exist."""if self.head.next == self.tail:return ""return next(iter(self.head.next.keys))
What We've Learned
- Pattern: Combine hash maps with doubly-linked list to maintain both O(1) lookup and ordered traversal
- Use Case: Essential for LFU cache, real-time leaderboards, and frequency-based analytics systems
- Optimization: Keys only move between adjacent count buckets, enabling efficient local list manipulation
- Trade-off: Uses O(n + k) space where n is keys and k is distinct counts, but achieves true O(1) operations
Problems to Practice
medium
Related problem that helps practice similar concepts and patterns.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid November, 2025
Staff
Mid November, 2025
Staff
Mid November, 2025
Atlassian
Senior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.