432. All O`one Data Structure

hard

Build a string counter supporting inc, dec, getMaxKey, and getMinKey — all in O(1). The trick: an ordered doubly-linked list of buckets, where each bucket holds all keys at the same count. The third-cousin of LFU Cache.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-25

Problem

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts. Implement the AllOne class: AllOne() initializes the object. inc(String key) increments the count of the string key by 1. If key does not exist, insert it with count 1. dec(String key) decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it. It is guaranteed that key exists before the decrement. getMaxKey() returns one of the keys with the maximal count. If no element exists, return an empty string. getMinKey() returns one of the keys with the minimum count. If no element exists, return an empty string. Each function must run in O(1) average time complexity.

Constraints

1 <= key.length <= 10
key consists of lowercase English letters.
It is guaranteed that for each call to dec, key exists in the data structure.
At most 5 * 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey.

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: After two inc('hello'), count(hello)=2 so max=min=hello. inc('leet') puts leet at count 1, hello stays at 2 → max=hello, min=leet.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Group keys by count into buckets, and chain buckets in a doubly-linked list ordered by count.

Hint 2

A hash map keyToBucket lets you find a key's bucket in O(1). Each bucket holds a hash set of keys at that count.

Hint 3

Min and max are just head.next and tail.prev of the bucket list — both O(1).

Solution approach

Reveal approach

Doubly-linked list of count-buckets plus key→bucket hash map. Each bucket holds (count, keys set, prev, next). Maintain head and tail sentinels; head.next is the lowest-count bucket, tail.prev is the highest. The hash map keyToBucket maps each tracked key to its current bucket. On inc(key): if the key has no bucket, place it in the bucket immediately after head (count 1); create that bucket if it doesn't exist or has count != 1. Otherwise let b = keyToBucket[key]; the target count is b.count + 1; if b.next is a bucket with that count, move key there, else insert a fresh bucket between b and b.next. Remove key from b; if b is now empty, unlink and free it. On dec(key): mirror — move to the bucket with count − 1 if any (or remove the key entirely if the count was 1). Both operations are O(1) because every step is a constant number of hash and linked-list mutations. getMaxKey returns any key from tail.prev (empty string if list is empty); getMinKey returns any key from head.next.

Complexity

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

Related patterns

linked-list
doubly-linked-list
hash-map
design

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

Amazon
Meta
Microsoft
Google

Practice these live with InterviewChamp.AI

Drill All O`one Data Structure and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →