432. All O(1) Data Structure

432

HardData Structure DesignDoubly linked list of count-buckets + hash mapOrdered buckets by count

All O(1) Data Structure

Design a data structure supporting four operations, each in O(1) average time: inc(key) increments the count of an existing key or inserts it with count 1; dec(key) decrements the count of a key (guaranteed present) and removes it if the count drops to 0; getMaxKey() returns any key with the largest count, or the empty string if empty; getMinKey() returns any key with the smallest count, or the empty string if empty.

Open official problem prompt ↗

In plain English

Track integer counts for many keys and instantly report a key with the highest and lowest count, all in constant time.

Picture it like this

Like ranked shelves numbered by score: each shelf holds all keys sharing that score, shelves sit in order, and bumping a key's score just slides it to the neighbouring shelf.

Example

Input: inc('hello'); inc('hello'); getMaxKey(); getMinKey(); inc('leet'); getMaxKey(); getMinKey()
Output: 'hello'; 'hello'; 'hello'; 'leet'
Why: After two incs, hello has count 2 (both max and min). Adding leet (count 1) makes hello the max and leet the min.

Constraints

1 <= key.length <= 10key consists of lowercase English lettersAt most 5 * 10^4 calls totaldec is only called on an existing keyEach operation must run in O(1) average time

Pattern lesson

See the pattern, then code

Ordered buckets by count

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Group keys into buckets by exact count and keep the buckets in a doubly linked list ordered by count; inc/dec move a key to the neighbouring bucket (count +/-1), which is always adjacent, so max is the last bucket and min is the first.

New words, made simpleKnow these before the algorithm

Count bucket: A node grouping all keys that currently share the same count.
Doubly linked list: Nodes with prev/next pointers so buckets can be inserted or removed in O(1).
Sentinel: Dummy head/tail nodes (-inf / +inf counts) that remove edge-case pointer checks.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash map of counts + scan for extremes

Violates the O(1) requirement for the extreme queries.

Store key->count and scan all entries for max/min on demand.

Time O(1) inc/dec but O(K) for getMax/getMinSpace O(K)

Heaps for max and min

Updates are logarithmic and lazy deletion gets messy - not O(1).

Maintain a max-heap and min-heap of counts alongside the map.

Time O(log K) per updateSpace O(K)

Best choiceOrdered doubly linked list of count buckets

Adjacency of count +/-1 makes every move constant time and extremes are the end buckets.

Keep buckets sorted by count; move keys between adjacent buckets on inc/dec.

Time O(1) all operationsSpace O(K)

The rule we keep true

Invariant

The linked list of real buckets is always in strictly increasing count order, and every key sits in exactly the bucket equal to its current count.

Why this is correct

Reasoning

inc/dec change a key's count by exactly one, so its new bucket is the immediate neighbour of its old bucket; inserting that neighbour if missing preserves sorted order in O(1), keeping the first and last real buckets as the true min and max.

The algorithm in three movesSay these aloud before coding

1Maintain a doubly linked list of nodes, each holding a count and a set of keys with that count, ordered by increasing count

node(2)={hello}, node(1)={leet}

2Keep a hash map from key to the node it currently lives in

key_node: hello->2, leet->1

3On inc/dec, move the key to the neighbouring count bucket, creating it if it does not exist, and delete a bucket that becomes empty

min=node(1), max=node(2)

4getMaxKey reads any key from the last real node; getMinKey reads from the first real node

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[cnt1: leet]0

[cnt2: hello]1

1 · Readnew key

2 · Askcount-1 bucket exists?

3 · Update statelist: [1:{hello}]

4 · Resultcreated, hello in count 1

Key takeaway

Buckets ordered by count: count-1 holds leet (min), count-2 holds hello (max).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 1-6Bucket node
Each node stores its count, a set of keys, and prev/next links.
2
Lines 9-15Sentinels + map
Head(-inf) and tail(+inf) bracket the list; key_node maps each key to its bucket.
3
Lines 17-24Splice helpers
_insert_after and _remove keep list edits O(1) and never touch the ends thanks to sentinels.
4
Lines 26-42inc
Move the key to the count+1 neighbour (creating it if needed) and drop the old bucket if empty.
5
Lines 44-56dec
Symmetric: drop to count-1, or remove the key entirely when its count hits 0.
6
Lines 58-66Extremes
Max is tail.prev, min is head.next; empty when they collapse onto the sentinels.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty structure: both getMaxKey and getMinKey return the empty string
A single key is simultaneously the max and the min
dec dropping a key to 0 removes it and may empty and delete its bucket
inc creating the very first count-1 bucket next to the head sentinel

Common beginner mistakes

Forgetting to delete an emptied bucket, corrupting min/max reads
Reading getMaxKey/getMinKey without guarding against the empty (sentinel-only) list
Relinking pointers incorrectly when splicing a new bucket between neighbours
Not using sentinels, which forces many null checks and off-by-one bugs

Check your understanding

Why must a key's new bucket after inc always be adjacent to its old bucket?

PyPython 3 · solution.py

Optimal

1class Node:2    def __init__(self, count: int):3        self.count = count4        self.keys = set()5        self.prev = None6        self.next = None78class AllOne:9    def __init__(self):10        self.head = Node(float('-inf'))11        self.tail = Node(float('inf'))12        self.head.next = self.tail13        self.tail.prev = self.head14        self.key_node: dict[str, Node] = {}1516    def _insert_after(self, node: Node, new: Node) -> None:17        new.prev, new.next = node, node.next18        node.next.prev = new19        node.next = new2021    def _remove(self, node: Node) -> None:22        node.prev.next = node.next23        node.next.prev = node.prev2425    def inc(self, key: str) -> None:26        if key in self.key_node:27            cur = self.key_node[key]28            cur.keys.remove(key)29            nxt = cur.next30            if nxt.count != cur.count + 1:31                nxt = Node(cur.count + 1)32                self._insert_after(cur, nxt)33            nxt.keys.add(key)34            self.key_node[key] = nxt35            if not cur.keys:36                self._remove(cur)37        else:38            first = self.head.next39            if first.count != 1:40                first = Node(1)41                self._insert_after(self.head, first)42            first.keys.add(key)43            self.key_node[key] = first4445    def dec(self, key: str) -> None:46        cur = self.key_node[key]47        cur.keys.remove(key)48        if cur.count == 1:49            del self.key_node[key]50        else:51            prv = cur.prev52            if prv.count != cur.count - 1:53                prv = Node(cur.count - 1)54                self._insert_after(cur.prev, prv)55            prv.keys.add(key)56            self.key_node[key] = prv57        if not cur.keys:58            self._remove(cur)5960    def getMaxKey(self) -> str:61        if self.tail.prev is self.head:62            return ""63        return next(iter(self.tail.prev.keys))6465    def getMinKey(self) -> str:66        if self.head.next is self.tail:67            return ""68        return next(iter(self.head.next.keys))

Time complexityO(1) per inc, dec, getMaxKey, getMinKeyOptimized

Space complexityO(K) for K distinct keysExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoftUber

All O(1) Data Structure

All O(1) Data Structure

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design