All O`one Data Structure

hard hash map linked list design doubly linked list

Problem

Design a data structure supporting inc(key), dec(key), getMaxKey(), getMinKey() — all in O(1) time. Use a doubly linked list of buckets, each holding the set of keys with a given count, kept sorted by count.

Inputinc("a"); inc("b"); inc("b"); inc("c"); inc("c"); inc("c")

OutputgetMaxKey() = "c"; getMinKey() = "a"

Buckets: {1: a} ↔ {2: b} ↔ {3: c}. Head ends are min/max.

operations (e.g. inc a; inc b; dec a; max)

from collections import OrderedDict

class AllOne:
    def __init__(self):
        # bucket: count -> set of keys (insertion ordered)
        self.buckets = OrderedDict()
        self.count = {}  # key -> count

    def inc(self, key):
        c = self.count.get(key, 0)
        self.count[key] = c + 1
        # remove from old bucket
        if c > 0:
            self.buckets[c].discard(key)
            if not self.buckets[c]: del self.buckets[c]
        self.buckets.setdefault(c + 1, set()).add(key)

    def dec(self, key):
        c = self.count[key]
        self.buckets[c].discard(key)
        if not self.buckets[c]: del self.buckets[c]
        if c == 1:
            del self.count[key]
        else:
            self.count[key] = c - 1
            self.buckets.setdefault(c - 1, set()).add(key)

    def getMaxKey(self):
        if not self.buckets: return ""
        c = max(self.buckets); return next(iter(self.buckets[c]))

    def getMinKey(self):
        if not self.buckets: return ""
        c = min(self.buckets); return next(iter(self.buckets[c]))

class AllOne {
  constructor() {
    this.buckets = new Map(); // count -> Set
    this.count = new Map();   // key -> count
  }
  inc(key) {
    const c = this.count.get(key) || 0;
    this.count.set(key, c + 1);
    if (c > 0) {
      this.buckets.get(c).delete(key);
      if (this.buckets.get(c).size === 0) this.buckets.delete(c);
    }
    if (!this.buckets.has(c + 1)) this.buckets.set(c + 1, new Set());
    this.buckets.get(c + 1).add(key);
  }
  dec(key) { /* symmetric */ }
  getMaxKey() { /* find largest count, return first key */ }
  getMinKey() { /* find smallest count, return first key */ }
}

class AllOne {
    static class Bucket { int count; LinkedHashSet<String> keys = new LinkedHashSet<>(); Bucket prev, next; Bucket(int c){count=c;} }
    Bucket head, tail; // sentinels
    Map<String, Bucket> keyToBucket = new HashMap<>();

    public AllOne() {
        head = new Bucket(0); tail = new Bucket(0);
        head.next = tail; tail.prev = head;
    }
    // inc/dec splice the key between adjacent buckets; create or delete buckets as needed
    public void inc(String key) { /* O(1) bucket move */ }
    public void dec(String key) { /* O(1) bucket move */ }
    public String getMaxKey() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); }
    public String getMinKey() { return head.next == tail ? "" : head.next.keys.iterator().next(); }
}

struct Bucket { int count; list<string> keys; };
class AllOne {
    list<Bucket> lst; // ascending by count
    unordered_map<string, list<Bucket>::iterator> keyToBucket;
public:
    void inc(string key) { /* move key forward; create/erase buckets */ }
    void dec(string key) { /* move key backward */ }
    string getMaxKey() { return lst.empty() ? "" : lst.back().keys.front(); }
    string getMinKey() { return lst.empty() ? "" : lst.front().keys.front(); }
};

Explanation

We need a structure where increasing a key's count, decreasing it, and reading the highest- and lowest-count keys are all O(1). A plain hash map gives fast counts but not fast min/max, so the trick is to group keys into buckets by count and keep those buckets in sorted order.

Two maps work together: count maps each key to its current count, and buckets maps each count value to the set of keys that have that count. The buckets are kept ordered by count, so the smallest and largest are at the two ends.

On inc(key), we read the old count c, remove the key from bucket c (deleting that bucket if it becomes empty), and add the key to bucket c+1, creating it if needed. dec(key) is the mirror image, moving the key from bucket c down to c-1 or dropping it entirely when the count hits zero.

Because every key sits in exactly the bucket of its count, getMaxKey just returns any key from the highest-count bucket and getMinKey returns one from the lowest, both at the ends of the ordering.

Example: incrementing a once, b twice, and c three times builds buckets {1: a} ↔ {2: b} ↔ {3: c}. So getMinKey() is "a" and getMaxKey() is "c". In an optimal implementation the buckets form a doubly linked list, making each move a constant-time splice.

Time: O(1) per op Space: O(n)