The Leetcode problem "All O`one Data Structure" asks you to design a data structure that supports the following operations in O(1) time:
inc(key): Increments the count of key by 1. If key does not exist, insert it with count 1.dec(key): Decrements the count of key by 1. If key's count becomes 0, remove it from the data structure.getMaxKey(): Returns one of the keys with the maximal count. If no keys exist, return an empty string.getMinKey(): Returns one of the keys with the minimal count. If no keys exist, return an empty string.
The challenge is to ensure all operations run in constant time, even as the number of keys grows. You may return any valid key for getMaxKey and getMinKey. Keys are strings, and counts are positive integers.
At first glance, the problem seems simple: we can use a hash map to store each key and its count. However, the real challenge lies in supporting getMaxKey() and getMinKey() in O(1) time. If we use only a hash map, we would need to scan all keys to find the max or min count, which is O(n).
To overcome this, we need a way to track keys by their counts efficiently, and quickly update this tracking as counts change. This leads us to consider combining a hash map (for O(1) key lookups and updates) with a doubly linked list (to maintain order of counts and allow O(1) insertions/deletions).
The conceptual leap is realizing we should not track individual keys in the list, but rather group keys by their counts in "buckets" and order these buckets by count. This way, we can always access the min and max count groups in O(1) time.
We construct a custom data structure using two main components:
keyCount maps each key to its count.
countBucket maps each count to a bucket node in a doubly linked list. Each bucket node contains a set of keys with that count.
The algorithm works as follows:
inc(key) is called:
key is new, insert it into the count 1 bucket. If this bucket doesn't exist, create it and add to the head of the list.key exists, move it from its current count bucket to the next higher count bucket (creating the bucket if needed), and remove it from the old bucket. If the old bucket is empty, remove it from the list.dec(key) is called:
key doesn't exist, do nothing.key from the data structure and its bucket. If the bucket is empty, remove it.key to the previous lower count bucket (creating it if necessary).getMaxKey() returns any key from the tail bucket (max count), or "" if empty.getMinKey() returns any key from the head bucket (min count), or "" if empty.The use of two hash maps and a doubly linked list ensures all operations are O(1): hash map lookups/updates are O(1), and linked list node insertions/removals are also O(1).
Let's walk through a sequence of operations:
inc("apple"): "apple" is new. Create count 1 bucket and add "apple".inc("banana"): "banana" is new. Add to existing count 1 bucket. Now, count 1 bucket has {"apple", "banana"}.inc("apple"): "apple" moves from count 1 to count 2. Remove "apple" from count 1 bucket, add to new count 2 bucket. Now, count 1 bucket has {"banana"}, count 2 bucket has {"apple"}.getMaxKey(): Returns "apple" (from count 2 bucket).getMinKey(): Returns "banana" (from count 1 bucket).dec("apple"): "apple" moves from count 2 to count 1. Remove from count 2 bucket, add to count 1 bucket. Now, count 2 bucket is empty and removed. Count 1 bucket has {"apple", "banana"}.getMaxKey(): Returns either "apple" or "banana" (both have count 1).At each step, all operations (move, insert, delete, get) are performed in constant time.
Brute-force Approach: If we used only a hash map, inc and dec would be O(1), but getMaxKey and getMinKey would be O(n) because we would need to scan all keys.
Optimized Approach (Bucket List):
inc, dec, getMaxKey, getMinKey) are O(1) because:
The "All O`one Data Structure" problem is a classic example of combining data structures for optimal efficiency. By grouping keys by counts in a doubly linked list of buckets and maintaining fast access with hash maps, we achieve O(1) operations for all required methods. The key insight is to avoid scanning for min/max by always keeping them at the ends of the list, and to carefully update our data structure as counts change.
This approach elegantly balances fast updates and queries, and is a powerful pattern for designing advanced data structures.
class Node:
def __init__(self, count):
self.count = count
self.keys = set()
self.prev = None
self.next = None
class AllOne:
def __init__(self):
self.keyCount = {} # key -> count
self.countBucket = {} # count -> Node
self.head = Node(float('-inf'))
self.tail = Node(float('inf'))
self.head.next = self.tail
self.tail.prev = self.head
def _addNodeAfter(self, newNode, prevNode):
nxt = prevNode.next
prevNode.next = newNode
newNode.prev = prevNode
newNode.next = nxt
nxt.prev = newNode
def _removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
del self.countBucket[node.count]
def inc(self, key: str) -> None:
count = self.keyCount.get(key, 0)
newCount = count + 1
self.keyCount[key] = newCount
if newCount not in self.countBucket:
newNode = Node(newCount)
self.countBucket[newCount] = newNode
if count == 0:
self._addNodeAfter(newNode, self.head)
else:
self._addNodeAfter(newNode, self.countBucket[count])
node = self.countBucket[newCount]
node.keys.add(key)
if count > 0:
prevNode = self.countBucket[count]
prevNode.keys.remove(key)
if not prevNode.keys:
self._removeNode(prevNode)
def dec(self, key: str) -> None:
if key not in self.keyCount:
return
count = self.keyCount[key]
node = self.countBucket[count]
node.keys.remove(key)
if count == 1:
del self.keyCount[key]
else:
newCount = count - 1
self.keyCount[key] = newCount
if newCount not in self.countBucket:
newNode = Node(newCount)
self.countBucket[newCount] = newNode
self._addNodeAfter(newNode, node.prev)
self.countBucket[newCount].keys.add(key)
if not node.keys:
self._removeNode(node)
def getMaxKey(self) -> str:
if self.tail.prev == self.head:
return ""
node = self.tail.prev
return next(iter(node.keys))
def getMinKey(self) -> str:
if self.head.next == self.tail:
return ""
node = self.head.next
return next(iter(node.keys))
class AllOne {
struct Node {
int count;
unordered_set<string> keys;
Node* prev;
Node* next;
Node(int c) : count(c), prev(nullptr), next(nullptr) {}
};
unordered_map<string, int> keyCount;
unordered_map<int, Node*> countBucket;
Node* head;
Node* tail;
public:
AllOne() {
head = new Node(INT_MIN);
tail = new Node(INT_MAX);
head->next = tail;
tail->prev = head;
}
void addNodeAfter(Node* newNode, Node* prevNode) {
Node* nxt = prevNode->next;
prevNode->next = newNode;
newNode->prev = prevNode;
newNode->next = nxt;
nxt->prev = newNode;
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
countBucket.erase(node->count);
delete node;
}
void inc(string key) {
int count = keyCount.count(key) ? keyCount[key] : 0;
int newCount = count + 1;
keyCount[key] = newCount;
if (!countBucket.count(newCount)) {
Node* newNode = new Node(newCount);
countBucket[newCount] = newNode;
if (count == 0)
addNodeAfter(newNode, head);
else
addNodeAfter(newNode, countBucket[count]);
}
countBucket[newCount]->keys.insert(key);
if (count > 0) {
Node* prevNode = countBucket[count];
prevNode->keys.erase(key);
if (prevNode->keys.empty())
removeNode(prevNode);
}
}
void dec(string key) {
if (!keyCount.count(key))
return;
int count = keyCount[key];
Node* node = countBucket[count];
node->keys.erase(key);
if (count == 1) {
keyCount.erase(key);
} else {
int newCount = count - 1;
keyCount[key] = newCount;
if (!countBucket.count(newCount)) {
Node* newNode = new Node(newCount);
countBucket[newCount] = newNode;
addNodeAfter(newNode, node->prev);
}
countBucket[newCount]->keys.insert(key);
}
if (node->keys.empty())
removeNode(node);
}
string getMaxKey() {
if (tail->prev == head)
return "";
return *(tail->prev->keys.begin());
}
string getMinKey() {
if (head->next == tail)
return "";
return *(head->next->keys.begin());
}
};
class AllOne {
private class Node {
int count;
Set<String> keys;
Node prev, next;
Node(int c) {
count = c;
keys = new HashSet<>();
}
}
private Map<String, Integer> keyCount = new HashMap<>();
private Map<Integer, Node> countBucket = new HashMap<>();
private Node head, tail;
public AllOne() {
head = new Node(Integer.MIN_VALUE);
tail = new Node(Integer.MAX_VALUE);
head.next = tail;
tail.prev = head;
}
private void addNodeAfter(Node newNode, Node prevNode) {
Node nxt = prevNode.next;
prevNode.next = newNode;
newNode.prev = prevNode;
newNode.next = nxt;
nxt.prev = newNode;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
countBucket.remove(node.count);
}
public void inc(String key) {
int count = keyCount.getOrDefault(key, 0);
int newCount = count + 1;
keyCount.put(key, newCount);
if (!countBucket.containsKey(newCount)) {
Node newNode = new Node(newCount);
countBucket.put(newCount, newNode);
if (count == 0)
addNodeAfter(newNode, head);
else
addNodeAfter(newNode, countBucket.get(count));
}
countBucket.get(newCount).keys.add(key);
if (count > 0) {
Node prevNode = countBucket.get(count);
prevNode.keys.remove(key);
if (prevNode.keys.isEmpty())
removeNode(prevNode);
}
}
public void dec(String key) {
if (!keyCount.containsKey(key))
return;
int count = keyCount.get(key);
Node node = countBucket.get(count);
node.keys.remove(key);
if (count == 1) {
keyCount.remove(key);
} else {
int newCount = count - 1;
keyCount.put(key, newCount);
if (!countBucket.containsKey(newCount)) {
Node newNode = new Node(newCount);
countBucket.put(newCount, newNode);
addNodeAfter(newNode, node.prev);
}
countBucket.get(newCount).keys.add(key);
}
if (node.keys.isEmpty())
removeNode(node);
}
public String getMaxKey() {
if (tail.prev == head)
return "";
return tail.prev.keys.iterator().next();
}
public String getMinKey() {
if (head.next == tail)
return "";
return head.next.keys.iterator().next();
}
}
class Node {
constructor(count) {
this.count = count;
this.keys = new Set();
this.prev = null;
this.next = null;
}
}
class AllOne {
constructor() {
this.keyCount = new Map();
this.countBucket = new Map();
this.head = new Node(-Infinity);
this.tail = new Node(Infinity);
this.head.next = this.tail;
this.tail.prev = this.head;
}
_addNodeAfter(newNode, prevNode) {
let nxt = prevNode.next;
prevNode.next = newNode;
newNode.prev = prevNode;
newNode.next = nxt;
nxt.prev = newNode;
}
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
this.countBucket.delete(node.count);
}
inc(key) {
let count = this.keyCount.has(key) ? this.keyCount.get(key) : 0;
let newCount = count + 1;
this.keyCount.set(key, newCount);
if (!this.countBucket.has(newCount)) {
let newNode = new Node(newCount);
this.countBucket.set(newCount, newNode);
if (count === 0) {
this._addNodeAfter(newNode, this.head);
} else {
this._addNodeAfter(newNode, this.countBucket.get(count));
}
}
let node = this.countBucket.get(newCount);
node.keys.add(key);
if (count > 0) {
let prevNode = this.countBucket.get(count);
prevNode.keys.delete(key);
if (prevNode.keys.size === 0) {
this._removeNode(prevNode);
}
}
}
dec(key) {
if (!this.keyCount.has(key)) return;
let count = this.keyCount.get(key);
let node = this.countBucket.get(count);
node.keys.delete(key);
if (count === 1) {
this.keyCount.delete(key);
} else {
let newCount = count - 1;
this.keyCount.set(key, newCount);
if (!this.countBucket.has(newCount)) {
let newNode = new Node(newCount);
this.countBucket.set(newCount, newNode);
this._addNodeAfter(newNode, node.prev);
}
this.countBucket.get(newCount).keys.add(key);
}
if (node.keys.size === 0) {
this._removeNode(node);
}
}
getMaxKey() {
if (this.tail.prev === this.head) return "";
return this.tail.prev.keys.values().next().value;
}
getMinKey() {
if (this.head.next === this.tail) return "";
return this.head.next.keys.values().next().value;
}
}