All O`one Data Structure
Description
Design a structure that counts strings and can return a string with the largest count and one with the smallest.
Implement the AllOne class:
AllOne()starts with no strings counted.void inc(string key)adds one tokey's count. A key that isn't counted yet starts at 1.void dec(string key)takes one fromkey's count. When it reaches 0, the key is no longer counted.keyis always counted whendecis called.string getMaxKey()returns one of the keys with the largest count, or an empty string if no key is counted.string getMinKey()returns one of the keys with the smallest count, or an empty string if no key is counted.
Each call must take O(1) time on average.
When several keys share the largest or the smallest count, any of them is a right answer. The tests only ask while one key has that count alone, so every answer has a single right value.
Examples
Example 1
Input:
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output: [null, null, null, "hello", "hello", null, "hello", "leet"]
Explanation: hello is counted twice, so it's both the largest and the smallest. leet comes in at 1: hello, at 2, is the largest, and leet the smallest.
Example 2
Input:
["AllOne", "inc", "dec", "getMaxKey", "getMinKey", "inc", "inc", "inc", "getMaxKey", "getMinKey", "dec", "dec", "getMaxKey"]
[[], ["a"], ["a"], [], [], ["b"], ["b"], ["c"], [], [], ["b"], ["b"], []]
Output: [null, null, null, "", "", null, null, null, "b", "c", null, null, "c"]
Explanation: a goes up to 1 and back to 0, so nothing is counted and both answers are empty strings. Then b reaches 2 and c 1; two decs take b back to 0, and c is the only key left.
Example 3
Input:
["AllOne", "inc", "inc", "inc", "inc", "inc", "getMaxKey", "getMinKey", "dec", "dec", "getMaxKey", "getMinKey"]
[[], ["x"], ["y"], ["y"], ["x"], ["x"], [], [], ["x"], ["x"], [], []]
Output: [null, null, null, null, null, null, "x", "y", null, null, "y", "x"]
Explanation: x reaches 3 and y 2, so x has the largest count and y the smallest. Two decs bring x down to 1, below y: now y is the largest and x the smallest.
Constraints
- 1 ≤ key.length ≤ 10
- key consists of lowercase English letters
- Every dec is called on a key that is counted
- At most 5 × 10⁴ calls are made to inc, dec, getMaxKey and getMinKey
Editorial
Brute Force
Intuition
Keep a count per key in a hash map: inc and dec are one update each, and a key whose count reaches 0 is deleted. For getMaxKey and getMinKey, read every key's count and answer with the largest or the smallest.
Step-by-Step Explanation
Let's trace Example 3:
inc("x")raises "x" to 1.inc("y")raises "y" to 1.inc("y")raises "y" to 2.inc("x")raises "x" to 2.inc("x")raises "x" to 3.getMaxKey()reads every count, 2 of them, and "x", at 3, is the largest.getMinKey()reads every count, 2 of them, and "y", at 2, is the smallest.dec("x")lowers "x" to 2.dec("x")lowers "x" to 1.getMaxKey()reads every count, 2 of them, and "y", at 2, is the largest.getMinKey()reads every count, 2 of them, and "x", at 1, is the smallest.
A Count per Key — inc and dec change one count; each question reads them all.
Algorithm
- Keep a hash map from each key to its count.
- inc adds 1 to
key's count, starting it at 1 when it's new; dec takes 1 off, and deleteskeyat 0. - getMaxKey and getMinKey read every count and return a key with the largest or the smallest, or an empty string when the map is empty.
Code
class AllOne {
unordered_map<string, int> count;
public:
AllOne() {
}
void inc(string key) {
count[key]++;
}
void dec(string key) {
if (--count[key] == 0) count.erase(key);
}
string getMaxKey() {
string best;
int most = 0;
for (auto& [key, c] : count) // every key, every time
if (c > most) most = c, best = key;
return best;
}
string getMinKey() {
string best;
int least = INT_MAX;
for (auto& [key, c] : count)
if (c < least) least = c, best = key;
return best;
}
};
class AllOne:
def __init__(self):
self.count = {}
def inc(self, key: str) -> None:
self.count[key] = self.count.get(key, 0) + 1
def dec(self, key: str) -> None:
self.count[key] -= 1
if self.count[key] == 0:
del self.count[key]
def getMaxKey(self) -> str:
return max(self.count, key=self.count.get) if self.count else "" # every key, every time
def getMinKey(self) -> str:
return min(self.count, key=self.count.get) if self.count else ""
class AllOne {
private final Map<String, Integer> count = new HashMap<>();
public AllOne() {
}
public void inc(String key) {
count.merge(key, 1, Integer::sum);
}
public void dec(String key) {
if (count.merge(key, -1, Integer::sum) == 0) count.remove(key);
}
public String getMaxKey() {
String best = "";
int most = 0;
for (Map.Entry<String, Integer> e : count.entrySet()) // every key, every time
if (e.getValue() > most) { most = e.getValue(); best = e.getKey(); }
return best;
}
public String getMinKey() {
String best = "";
int least = Integer.MAX_VALUE;
for (Map.Entry<String, Integer> e : count.entrySet())
if (e.getValue() < least) { least = e.getValue(); best = e.getKey(); }
return best;
}
}
var AllOne = function() {
this.count = new Map();
};
AllOne.prototype.inc = function(key) {
this.count.set(key, (this.count.get(key) ?? 0) + 1);
};
AllOne.prototype.dec = function(key) {
const c = this.count.get(key) - 1;
if (c === 0) this.count.delete(key);
else this.count.set(key, c);
};
AllOne.prototype.getMaxKey = function() {
let best = "", most = 0;
for (const [key, c] of this.count) if (c > most) { most = c; best = key; } // every key, every time
return best;
};
AllOne.prototype.getMinKey = function() {
let best = "", least = Infinity;
for (const [key, c] of this.count) if (c < least) { least = c; best = key; }
return best;
};
Complexity Analysis
Time Complexity: O(1) for inc and dec, O(n) for each question
A question reads the counts of all n keys.
Space Complexity: O(n)
One count per key.
Why This Approach Is Not Efficient
Every question reads every key. With 5,000 keys counted and 5,000 questions, the scans took 1.92 s in Python on the judge, against 90 ms for the buckets below. But a count only ever moves by one: a key at 5 goes to 4 or 6. If the keys were kept in order of their counts, each call would only move a key to a neighbour, and the smallest and largest would sit at the two ends.
Optimal Approach - Buckets by Count
Intuition
Keep the counts themselves in a doubly linked list of buckets, in increasing order, each bucket holding the keys that have its count, and a map from each key to its bucket. inc moves a key one bucket over: into the next bucket when its count is one more, or into a new bucket linked in right after. A bucket that empties is unlinked. dec moves the other way, and a key at 1 simply leaves. The first bucket holds the smallest count and the last the largest, so each question reads one end. Two sentinels, head and tail, keep the ends simple.
Step-by-Step Explanation
Let's trace Example 3 again:
inc("x"): a bucket for count 1 is linked in right after head, and "x" goes into it.inc("y"): "y" joins the bucket of count 1.inc("y"): a bucket for count 2 is linked in next to count 1, and "y" goes into it.inc("x"): "x" joins the bucket of count 2, and the emptied bucket of count 1 is unlinked.inc("x"): a bucket for count 3 is linked in next to count 2, and "x" goes into it.getMaxKey()reads the bucket before tail, count 3: "x".getMinKey()reads the bucket after head, count 2: "y".dec("x"): "x" joins the bucket of count 2, and the emptied bucket of count 3 is unlinked.dec("x"): a bucket for count 1 is linked in right after head, and "x" goes into it.getMaxKey()reads the bucket before tail, count 2: "y".getMinKey()reads the bucket after head, count 1: "x".
Buckets by Count — Each call moves one key at most one bucket over; the two ends answer the questions.
Algorithm
- Keep a doubly linked list of buckets between a head and a tail, counts increasing, each bucket a count and a set of keys, and a map from each key to its bucket. A new key counts as being in head, count 0.
- inc: if the bucket after the key's is one count more, move the key there; otherwise link a new bucket in right after and move it there. If the old bucket is now empty, unlink it.
- dec: at count 1, delete the key from the map. Otherwise move it into the bucket before, or into a new one linked in before when that bucket isn't one count less. Unlink the old bucket if it's empty.
- getMaxKey returns a key of the bucket before tail and getMinKey one of the bucket after head, or an empty string when there's no bucket.
Code
class AllOne {
struct Bucket {
int count;
unordered_set<string> keys;
};
list<Bucket> buckets; // counts increasing from the front
unordered_map<string, list<Bucket>::iterator> where; // key -> the bucket holding it
public:
AllOne() {
}
void inc(string key) {
auto it = where.find(key);
if (it == where.end()) { // a new key: count 1, at the front
if (buckets.empty() || buckets.front().count != 1) buckets.push_front({1, {}});
buckets.front().keys.insert(key);
where[key] = buckets.begin();
return;
}
auto b = it->second, nxt = next(b);
if (nxt == buckets.end() || nxt->count != b->count + 1) nxt = buckets.insert(nxt, {b->count + 1, {}});
nxt->keys.insert(key);
where[key] = nxt;
b->keys.erase(key);
if (b->keys.empty()) buckets.erase(b);
}
void dec(string key) {
auto b = where[key];
if (b->count == 1) {
where.erase(key);
} else {
auto prv = b == buckets.begin() ? buckets.end() : prev(b);
if (prv == buckets.end() || prv->count != b->count - 1) prv = buckets.insert(b, {b->count - 1, {}});
prv->keys.insert(key);
where[key] = prv;
}
b->keys.erase(key);
if (b->keys.empty()) buckets.erase(b);
}
string getMaxKey() {
return buckets.empty() ? "" : *buckets.back().keys.begin();
}
string getMinKey() {
return buckets.empty() ? "" : *buckets.front().keys.begin();
}
};
class Bucket:
def __init__(self, count):
self.count = count
self.keys = set()
self.prev = self.next = None
class AllOne:
def __init__(self):
self.head, self.tail = Bucket(0), Bucket(0) # sentinels: the buckets run between them, counts increasing
self.head.next, self.tail.prev = self.tail, self.head
self.bucket = {} # key -> the bucket holding it
def insert_after(self, b, count):
fresh = Bucket(count)
fresh.prev, fresh.next = b, b.next
b.next.prev = fresh
b.next = fresh
return fresh
def unlink(self, b):
b.prev.next, b.next.prev = b.next, b.prev
def inc(self, key: str) -> None:
b = self.bucket.get(key, self.head) # a new key starts from count 0, the head
nxt = b.next
if nxt is self.tail or nxt.count != b.count + 1:
nxt = self.insert_after(b, b.count + 1)
nxt.keys.add(key)
self.bucket[key] = nxt
if b is not self.head:
b.keys.remove(key)
if not b.keys:
self.unlink(b)
def dec(self, key: str) -> None:
b = self.bucket[key]
if b.count == 1:
del self.bucket[key]
else:
prv = b.prev
if prv is self.head or prv.count != b.count - 1:
prv = self.insert_after(b.prev, b.count - 1)
prv.keys.add(key)
self.bucket[key] = prv
b.keys.remove(key)
if not b.keys:
self.unlink(b)
def getMaxKey(self) -> str:
return next(iter(self.tail.prev.keys)) if self.tail.prev is not self.head else ""
def getMinKey(self) -> str:
return next(iter(self.head.next.keys)) if self.head.next is not self.tail else ""
class AllOne {
private static class Bucket {
final int count;
final Set<String> keys = new HashSet<>();
Bucket prev, next;
Bucket(int count) {
this.count = count;
}
}
private final Bucket head = new Bucket(0), tail = new Bucket(0); // sentinels: counts increase between them
private final Map<String, Bucket> bucket = new HashMap<>(); // key -> the bucket holding it
public AllOne() {
head.next = tail;
tail.prev = head;
}
private Bucket insertAfter(Bucket b, int count) {
Bucket fresh = new Bucket(count);
fresh.prev = b;
fresh.next = b.next;
b.next.prev = fresh;
b.next = fresh;
return fresh;
}
private void unlink(Bucket b) {
b.prev.next = b.next;
b.next.prev = b.prev;
}
public void inc(String key) {
Bucket b = bucket.getOrDefault(key, head); // a new key starts from count 0, the head
Bucket nxt = b.next;
if (nxt == tail || nxt.count != b.count + 1) nxt = insertAfter(b, b.count + 1);
nxt.keys.add(key);
bucket.put(key, nxt);
if (b != head) {
b.keys.remove(key);
if (b.keys.isEmpty()) unlink(b);
}
}
public void dec(String key) {
Bucket b = bucket.get(key);
if (b.count == 1) {
bucket.remove(key);
} else {
Bucket prv = b.prev;
if (prv == head || prv.count != b.count - 1) prv = insertAfter(b.prev, b.count - 1);
prv.keys.add(key);
bucket.put(key, prv);
}
b.keys.remove(key);
if (b.keys.isEmpty()) unlink(b);
}
public String getMaxKey() {
return tail.prev == head ? "" : tail.prev.keys.iterator().next();
}
public String getMinKey() {
return head.next == tail ? "" : head.next.keys.iterator().next();
}
}
var AllOne = function() {
this.head = { count: 0, keys: new Set(), prev: null, next: null }; // sentinels: counts increase between them
this.tail = { count: 0, keys: new Set(), prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
this.bucket = new Map(); // key -> the bucket holding it
};
AllOne.prototype.insertAfter = function(b, count) {
const fresh = { count, keys: new Set(), prev: b, next: b.next };
b.next.prev = fresh;
b.next = fresh;
return fresh;
};
AllOne.prototype.unlink = function(b) {
b.prev.next = b.next;
b.next.prev = b.prev;
};
AllOne.prototype.inc = function(key) {
const b = this.bucket.get(key) ?? this.head; // a new key starts from count 0, the head
let nxt = b.next;
if (nxt === this.tail || nxt.count !== b.count + 1) nxt = this.insertAfter(b, b.count + 1);
nxt.keys.add(key);
this.bucket.set(key, nxt);
if (b !== this.head) {
b.keys.delete(key);
if (b.keys.size === 0) this.unlink(b);
}
};
AllOne.prototype.dec = function(key) {
const b = this.bucket.get(key);
if (b.count === 1) {
this.bucket.delete(key);
} else {
let prv = b.prev;
if (prv === this.head || prv.count !== b.count - 1) prv = this.insertAfter(b.prev, b.count - 1);
prv.keys.add(key);
this.bucket.set(key, prv);
}
b.keys.delete(key);
if (b.keys.size === 0) this.unlink(b);
};
AllOne.prototype.getMaxKey = function() {
return this.tail.prev === this.head ? "" : this.tail.prev.keys.values().next().value;
};
AllOne.prototype.getMinKey = function() {
return this.head.next === this.tail ? "" : this.head.next.keys.values().next().value;
};
Complexity Analysis
Time Complexity: O(1) per call
A call moves one key between two neighbouring buckets, linking or unlinking at most one; the questions read one end. Hash operations are O(1) on average.
Space Complexity: O(n)
Each key is in one bucket, and there are at most as many buckets as keys.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Leaving an emptied bucket in the list. b.keys.remove(key)
On the calls below it fails with StopIteration instead of returning [null, null, null, ""].
["AllOne", "inc", "dec", "getMaxKey"]
[[], ["a"], ["a"], []]
When dec takes the last key out of a bucket, the bucket has to leave the list too. Left behind at either end, it's what getMaxKey or getMinKey reads next, and it holds no key to give.
Putting a new key in the first bucket. if nxt is self.tail or (b is not self.head and nxt.count != b.count + 1):
On the calls below it returns [null, null, null, null, null, null, "b"]; the answer is [null, null, null, null, null, null, "a"].
["AllOne", "inc", "inc", "inc", "inc", "inc", "getMaxKey"]
[[], ["a"], ["a"], ["a"], ["b"], ["b"], []]
A new key's count is 1, so it belongs in a bucket of count 1. The first bucket holds the smallest count, which isn't 1 once every key has been counted more than once: the new key would start at that count instead.
dec dropping the key into whatever bucket is below. if prv is self.head:
On the calls below it returns [null, null, null, null, null, null, null, null, ""]; the answer is [null, null, null, null, null, null, null, null, "b"].
["AllOne", "inc", "inc", "inc", "inc", "dec", "dec", "dec", "getMinKey"]
[[], ["x"], ["b"], ["b"], ["b"], ["b"], ["x"], ["b"], []]
After dec, the key's count is one less, so it goes in the bucket of exactly that count. The bucket below may be several counts lower; joining it lowers the key's count by more than one, and a later dec can take it out while it should still be counted.
Where This Pattern Is Taught
This problem practises keeping the counts themselves in order, as a linked list of buckets with a map from each key to its bucket, so each call is a step to a neighbouring bucket. It's taught in Designing a Data Structure.