All O`one Data Structure

HardProblemExternal linkUpdated Nov 9, 2026

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 to key's count. A key that isn't counted yet starts at 1.
void dec(string key) takes one from key's count. When it reaches 0, the key is no longer counted. key is always counted when dec is 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 deletes key at 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.