Leetcode 432. All O`one Data Structure
Asked at:
Atlassian
Meta
DESCRIPTION
Design a data structure that maintains string keys with integer counts and supports four operations in O(1) average time: increment a key's count (inc(key)), decrement a key's count (dec(key), removing the key when count reaches zero), retrieve any key with the maximum count (getMaxKey()), and retrieve any key with the minimum count (getMinKey()). For example, after inc("apple"), inc("apple"), inc("banana"), calling getMaxKey() should return "apple" (count 2) and getMinKey() should return "banana" (count 1).
Input:
inc("hello") inc("hello") inc("world") getMaxKey() getMinKey() dec("hello") getMaxKey()
Output:
null null null "hello" "world" null "hello" or "world"
Explanation: After two inc("hello"), hello has count 2. After inc("world"), world has count 1. getMaxKey() returns "hello" (count 2), getMinKey() returns "world" (count 1). After dec("hello"), both have count 1, so getMaxKey() can return either.
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
- If multiple keys have the same max/min count, return any one of them
Understanding the Problem
The core challenge is maintaining both key-to-count mappings and count-to-keys groupings while supporting O(1) operations. A simple hash map tracks counts but requires O(n) to find min/max. The key insight is using a doubly-linked list of count buckets, where each bucket stores all keys with that count. This allows O(1) navigation to adjacent counts when incrementing/decrementing, and O(1) access to min/max via list head/tail.
Building Intuition
A naive approach uses a hash map for key counts and scans all values to find min/max, taking O(n) time. A better approach maintains a doubly-linked list of count nodes, where each node represents a count value and stores all keys at that count. When incrementing "apple" from count 2 to 3, we move it from the count-2 node to the count-3 node (creating the node if needed), which takes O(1) since we can navigate to adjacent counts. For example, if we have counts [1→2→5], incrementing a key at count 2 creates or finds the count-3 node between 2 and 5.
This pattern appears in real-time analytics systems (tracking top/bottom performers), cache implementations (LFU eviction policies), and leaderboard systems (finding highest/lowest scores). The O(1) constraint is critical for high-throughput systems where millions of updates occur per second. Understanding this hybrid data structure approach (combining hash maps with linked lists) is essential for designing efficient systems that need both fast lookups and ordered access.
Common Pitfalls
Implementation
Count Bucket Node Structure
Define the doubly-linked list node that represents a single count value. Each CountNode stores the count value, a set of keys at that count (for O(1) add/remove), and pointers to previous/next count nodes. For example, a count-3 node might contain {"apple", "banana"} and link to count-2 and count-4 nodes. This structure enables O(1) navigation between adjacent counts when keys are incremented or decremented.
class CountNode:def __init__(self, count):self.count = countself.keys = set()self.prev = Noneself.next = None
Core Data Structure and Key Tracking
Implement the main data structure with three hash maps: keyCount (maps each key to its current count), keyNode (maps each key to its CountNode for O(1) access), and maintain head/tail pointers to the doubly-linked list for O(1) min/max access. For example, after inc("apple") twice, keyCount["apple"] = 2 and keyNode["apple"] points to the count-2 node. The head pointer always references the minimum count node, and tail references the maximum.
class AllOne:def __init__(self):self.keyCount = {}self.keyNode = {}self.head = Noneself.tail = None
Increment and Count Node Management
Implement inc(key) by moving the key from its current count node to the next count node. If the key is new, add it to the count-1 node (creating if needed). If moving from count c to c+1, check if a count-(c+1) node exists after the current node; if not, create and insert it between current and next. Remove the key from the old node's set, and if that set becomes empty, delete the old node from the linked list. For example, incrementing "apple" from count 2 to 3 moves it from the count-2 node to count-3 node, potentially creating the count-3 node.
def inc(self, key: str) -> None:if key in self.keyCount:count = self.keyCount[key]node = self.keyNode[key]self.keyCount[key] = count + 1if node.next is None or node.next.count != count + 1:newNode = CountNode(count + 1)newNode.prev = nodenewNode.next = node.nextif node.next:node.next.prev = newNodeelse:self.tail = newNodenode.next = newNodenode.next.keys.add(key)self.keyNode[key] = node.nextnode.keys.remove(key)if not node.keys:if node.prev:node.prev.next = node.nextelse:self.head = node.nextif node.next:node.next.prev = node.prevelse:self.tail = node.prevelse:self.keyCount[key] = 1if self.head is None or self.head.count != 1:newNode = CountNode(1)newNode.next = self.headif self.head:self.head.prev = newNodeelse:self.tail = newNodeself.head = newNodeself.head.keys.add(key)self.keyNode[key] = self.head
Decrement and Key Removal
Implement dec(key) by moving the key to the previous count node, or removing it entirely if count becomes 0. If decrementing from count c to c-1, check if a count-(c-1) node exists before the current node; if not and c > 1, create and insert it. Remove the key from the old node's set and delete the old node if empty. If the new count is 0, remove the key from all maps (keyCount and keyNode). For example, decrementing "banana" from count 1 removes it completely from the data structure.
def dec(self, key: str) -> None:if key not in self.keyCount:returncount = self.keyCount[key]node = self.keyNode[key]if count == 1:del self.keyCount[key]del self.keyNode[key]node.keys.remove(key)else:self.keyCount[key] = count - 1if node.prev is None or node.prev.count != count - 1:newNode = CountNode(count - 1)newNode.next = nodenewNode.prev = node.previf node.prev:node.prev.next = newNodeelse:self.head = newNodenode.prev = newNodenode.prev.keys.add(key)self.keyNode[key] = node.prevnode.keys.remove(key)if not node.keys:if node.prev:node.prev.next = node.nextelse:self.head = node.nextif node.next:node.next.prev = node.prevelse:self.tail = node.prev
Min/Max Key Retrieval
Implement getMinKey() and getMaxKey() using the head and tail pointers. Since head always points to the minimum count node and tail to the maximum, simply return any key from the respective node's key set (use set iteration to get one element). Return an empty string if head or tail is null (no keys exist). For example, if the list is [count-1: {"world"} → count-3: {"apple", "banana"}], getMinKey() returns "world" and getMaxKey() returns either "apple" or "banana".
def getMaxKey(self) -> str:if self.tail is None:return ""return next(iter(self.tail.keys))def getMinKey(self) -> str:if self.head is None:return ""return next(iter(self.head.keys))
What We've Learned
- Pattern: Combine hash maps with doubly-linked lists to achieve O(1) operations for both direct access and ordered traversal
- Use Case: Essential for LFU caches, real-time leaderboards, and analytics systems requiring instant min/max queries
- Design Principle: Maintain bidirectional pointers (key→node and node→keys) to enable O(1) updates in both directions
- Memory Management: Always remove empty count nodes to prevent memory leaks in long-running systems
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.
Early March, 2026
Staff
Mid January, 2026
Atlassian
Senior
Late December, 2025
Staff
Hello Interview Premium
Your account is free and you can post anonymously if you choose.