All O’s One Data Structure
XXX. All O(1) Data Structure
Data Structure
Linked List
HashMap
Problem Statement:
Design a data structure that supports all following operations in O(1) time:
- inc(key): Inserts a new key with value 1 or increments existing key by 1
- dec(key): Decrements existing key by 1. If key's value is 1, removes it
- getMaxKey(): Returns one of the keys with maximal value
- getMinKey(): Returns one of the keys with minimal value
Implementation:
Java Solution:
public class AllOne {
// Bucket node for doubly linked list
private class Bucket {
int count; // Count for this bucket
Set keySet; // Set of keys with this count
Bucket next; // Next bucket (higher count)
Bucket pre; // Previous bucket (lower count)
public Bucket(int cnt) {
count = cnt;
keySet = new HashSet<>(); // Using HashSet for O(1) operations
}
}
// Core data structure components
private Bucket head; // Dummy head (min sentinel)
private Bucket tail; // Dummy tail (max sentinel)
private Map countBucketMap; // Maps count to bucket
private Map keyCountMap; // Maps key to its count
public AllOne() {
// Initialize with sentinel nodes
head = new Bucket(Integer.MIN_VALUE);
tail = new Bucket(Integer.MAX_VALUE);
head.next = tail;
tail.pre = head;
countBucketMap = new HashMap<>();
keyCountMap = new HashMap<>();
}
public void inc(String key) {
if (keyCountMap.containsKey(key)) {
// Key exists: increment its count
changeKey(key, 1);
} else {
// New key: initialize with count 1
keyCountMap.put(key, 1);
// Create bucket of count 1 if needed
if (head.next.count != 1) {
addBucketAfter(new Bucket(1), head);
}
head.next.keySet.add(key);
countBucketMap.put(1, head.next);
}
}
public void dec(String key) {
if (keyCountMap.containsKey(key)) {
int count = keyCountMap.get(key);
if (count == 1) {
// Remove key if count becomes 0
keyCountMap.remove(key);
removeKeyFromBucket(countBucketMap.get(count), key);
} else {
// Decrement key's count
changeKey(key, -1);
}
}
}
public String getMaxKey() {
// Return any key from the last non-sentinel bucket
return tail.pre == head ? "" : tail.pre.keySet.iterator().next();
}
public String getMinKey() {
// Return any key from the first non-sentinel bucket
return head.next == tail ? "" : head.next.keySet.iterator().next();
}
// Helper method to change key's count by offset
private void changeKey(String key, int offset) {
int count = keyCountMap.get(key);
keyCountMap.put(key, count + offset);
Bucket curBucket = countBucketMap.get(count);
Bucket newBucket;
if (countBucketMap.containsKey(count + offset)) {
// Bucket for new count exists
newBucket = countBucketMap.get(count + offset);
} else {
// Create new bucket for the count
newBucket = new Bucket(count + offset);
countBucketMap.put(count + offset, newBucket);
// Add bucket in correct position
addBucketAfter(newBucket, offset == 1 ? curBucket : curBucket.pre);
}
// Move key to new bucket
newBucket.keySet.add(key);
removeKeyFromBucket(curBucket, key);
}
// Remove key from bucket and clean up if bucket becomes empty
private void removeKeyFromBucket(Bucket bucket, String key) {
bucket.keySet.remove(key);
if (bucket.keySet.isEmpty()) {
removeBucketFromList(bucket);
countBucketMap.remove(bucket.count);
}
}
// Remove bucket from doubly linked list
private void removeBucketFromList(Bucket bucket) {
bucket.pre.next = bucket.next;
bucket.next.pre = bucket.pre;
bucket.next = null; // Help GC
bucket.pre = null;
}
// Add newBucket after preBucket in the list
private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
newBucket.pre = preBucket;
newBucket.next = preBucket.next;
preBucket.next.pre = newBucket;
preBucket.next = newBucket;
}
}
Python Solution:
class Bucket:
def __init__(self, cnt):
self.count = cnt # Count for this bucket
self.keys = set() # Set of keys with this count
self.next = None # Next bucket (higher count)
self.prev = None # Previous bucket (lower count)
class AllOne:
def __init__(self):
# Initialize sentinel nodes
self.head = Bucket(float('-inf'))
self.tail = Bucket(float('inf'))
self.head.next = self.tail
self.tail.prev = self.head
# Maps for O(1) access
self.count_bucket = {} # Count to bucket mapping
self.key_count = {} # Key to count mapping
def _add_bucket_after(self, new_bucket, prev_bucket):
# Add new_bucket after prev_bucket
new_bucket.prev = prev_bucket
new_bucket.next = prev_bucket.next
prev_bucket.next.prev = new_bucket
prev_bucket.next = new_bucket
def _remove_bucket(self, bucket):
# Remove bucket from list
bucket.prev.next = bucket.next
bucket.next.prev = bucket.prev
def _change_key(self, key, offset):
# Change key's count by offset
count = self.key_count[key]
new_count = count + offset
self.key_count[key] = new_count
# Handle bucket changes
curr_bucket = self.count_bucket[count]
next_bucket = None
if new_count in self.count_bucket:
next_bucket = self.count_bucket[new_count]
else:
next_bucket = Bucket(new_count)
self._add_bucket_after(next_bucket,
curr_bucket if offset == 1 else curr_bucket.prev)
self.count_bucket[new_count] = next_bucket
# Move key to new bucket
curr_bucket.keys.remove(key)
next_bucket.keys.add(key)
# Clean up empty bucket
if not curr_bucket.keys:
self._remove_bucket(curr_bucket)
del self.count_bucket[count]
def inc(self, key: str) -> None:
if key in self.key_count:
self._change_key(key, 1)
else:
self.key_count[key] = 1
if self.head.next.count != 1:
self._add_bucket_after(Bucket(1), self.head)
self.count_bucket[1] = self.head.next
self.head.next.keys.add(key)
self.count_bucket[1] = self.head.next
def dec(self, key: str) -> None:
if key in self.key_count:
count = self.key_count[key]
if count == 1:
del self.key_count[key]
bucket = self.count_bucket[count]
bucket.keys.remove(key)
if not bucket.keys:
self._remove_bucket(bucket)
del self.count_bucket[count]
else:
self._change_key(key, -1)
def getMaxKey(self) -> str:
if self.tail.prev == self.head:
return ""
return next(iter(self.tail.prev.keys))
def getMinKey(self) -> str:
if self.head.next == self.tail:
return ""
return next(iter(self.head.next.keys))
C++ Solution:
class AllOne {
// Bucket structure for linked list
struct Bucket {
int count; // Count for this bucket
unordered_set keys; // Set of keys with this count
Bucket *next, *prev; // Pointers for doubly linked list
Bucket(int cnt): count(cnt) {} // Constructor
};
// Core data members
Bucket *head, *tail; // Sentinel nodes
unordered_map countBucket; // Count to bucket mapping
unordered_map keyCount; // Key to count mapping
// Helper to add newBucket after prevBucket
void addBucketAfter(Bucket* newBucket, Bucket* prevBucket) {
newBucket->prev = prevBucket;
newBucket->next = prevBucket->next;
prevBucket->next->prev = newBucket;
prevBucket->next = newBucket;
}
// Helper to remove bucket from list
void removeBucket(Bucket* bucket) {
bucket->prev->next = bucket->next;
bucket->next->prev = bucket->prev;
delete bucket; // Free memory in C++
}
// Helper to change key's count
void changeKey(string& key, int offset) {
int count = keyCount[key];
int newCount = count + offset;
keyCount[key] = newCount;
Bucket* currBucket = countBucket[count];
Bucket* nextBucket;
if (countBucket.count(newCount)) {
nextBucket = countBucket[newCount];
} else {
nextBucket = new Bucket(newCount);
countBucket[newCount] = nextBucket;
addBucketAfter(nextBucket, offset == 1 ? currBucket : currBucket->prev);
}
nextBucket->keys.insert(key);
currBucket->keys.erase(key);
if (currBucket->keys.empty()) {
countBucket.erase(count);
removeBucket(currBucket);
}
}
public:
AllOne() {
// Initialize with sentinel nodes
head = new Bucket(INT_MIN);
tail = new Bucket(INT_MAX);
head->next = tail;
tail->prev = head;
}
~AllOne() {
// Clean up memory
while (head) {
Bucket* next = head->next;
delete head;
head = next;
}
}
void inc(string key) {
if (keyCount.count(key)) {
changeKey(key, 1);
} else {
keyCount[key] = 1;
if (head->next->count != 1) {
Bucket* bucket = new Bucket(1);
addBucketAfter(bucket, head);
countBucket[1] = bucket;
}
head->next->keys.insert(key);
countBucket[1] = head->next;
}
}
void dec(string key) {
if (keyCount.count(key)) {
int count = keyCount[key];
if (count == 1) {
keyCount.erase(key);
Bucket* bucket = countBucket[1];
bucket->keys.erase(key);
if (bucket->keys.empty()) {
countBucket.erase(1);
removeBucket(bucket);
}
} else {
changeKey(key, -1);
}
}
}
string getMaxKey() {
return tail->prev == head ? "" : *tail->prev->keys.begin();
}
string getMinKey() {
return head->next == tail ? "" : *head->next->keys.begin();
}
};
