Abstract / Summary

Implement a data structure that supports incrementing keys by one and retrieving keys with values at specific counts efficiently.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 44% (400k+ submissions).

Typical patterns to solve this problem:

• Design
• Doubly Linked List
• Hash Table
• Linked List

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The AllOne class implements a data structure that tracks integer counts for arbitrary string keys while providing constant-time access to a key with the maximum count and a key with the minimum count. Internally it stores a mapping from each key to its current count and a reverse mapping from each count value to the set of keys that share that count. Two integer fields, high and low, keep the current extreme count values, allowing the getMaxKey and getMinKey operations to return a result without scanning the entire collection.

Core Components

Initialization

The constructor creates three attributes. self.count is a plain dictionary that maps a key to its numeric count. self.classes is a defaultdict of sets, where each set holds the keys that have the same count. self.high and self.low are integer markers for the highest and lowest count currently present.

def __init__(self):
    self.count   = { }              # each key and its count
    self.classes = defaultdict(set) # classes[i] contains all keys with count i
    self.high = 0                   # highest count
    self.low  = 0                   # lowest count

Increment (inc)

When a key already exists, the method removes the key from the set belonging to its old count, adds it to the set for the incremented count, and updates the stored count. The high pointer is advanced if the incremented key was the sole holder of the previous maximum. The low pointer is advanced when the key being incremented was the only member of the current minimum count.

If the key is new, it is placed in the set for count 1, the dictionary entry is created, and both high and low are set to 1 (or left unchanged if a higher maximum already exists).

def inc(self, key: str) -> None:
    if key in self.count:
        # existing
        count = self.count[key]
        self.classes[count].discard(key)
        self.classes[count + 1].add(key)
        self.count[key] += 1

        if self.high == count:
            self.high += 1
        if self.low  == count and not self.classes[count]:
            self.low  += 1
    else:
        # new key
        self.classes[1].add(key)
        self.count[key] = 1

        if self.high == 0:
            self.high = 1
        self.low  = 1

Decrement (dec)

The method first removes the key from the set of its current count. If the count is greater than 1, the key is added to the set for the decremented count and its stored count is reduced. When the count reaches 1, the key is removed entirely from self.count and from the count-1 set.

After the removal, the high pointer is lowered if the key being decremented was the last holder of the previous maximum. The low pointer is decreased when the key being decremented was at the current minimum. If decreasing low would make it zero, a small linear scan is performed to locate the next non-empty count bucket; this scan is bounded by the number of distinct count values and is only triggered when the minimum bucket becomes empty.

def dec(self, key: str) -> None:
    count = self.count[key]
    self.classes[count].discard(key)

    if count > 1:
        self.classes[count - 1].add(key)
        self.count[key] -= 1
    else:
        # remove
        self.classes[1].discard(key)
        del self.count[key]

    if self.high == count and not self.classes[count]:
        self.high -= 1
    if self.low  == count:
        self.low  -= 1
        if self.low == 0:
            # strictly speaking not O(1)
            if self.count:
                self.low = 1
                while not self.classes[self.low]:
                    self.low += 1

Retrieve Maximum Key (getMaxKey)

The method checks whether a maximum count exists and whether its bucket is non-empty. If so, it returns an arbitrary element from the set, which is achieved by iterating once over the set and returning the first encountered key.

def getMaxKey(self) -> str:
    if self.high == 0 or not self.classes[self.high]:
        return ""
    for x in self.classes[self.high]:
        return x # return first element

Retrieve Minimum Key (getMinKey)

Analogous to getMaxKey, this method returns a key from the bucket identified by self.low. It also guards against the case where the minimum bucket is empty.

def getMinKey(self) -> str:
    if self.low == 0 or not self.classes[self.low]:
        return ""
    for x in self.classes[self.low]:
        return x # return first element

Edge Cases Handled

The implementation explicitly addresses several boundary conditions. When incrementing a key that does not yet exist, the structure initializes both extreme pointers to 1, ensuring that subsequent maximum and minimum queries are valid. When decrementing a key whose count drops to zero, the key is fully removed from both the forward and reverse mappings, preventing stale entries. The low pointer includes a fallback loop that searches forward from 1 until it finds a non-empty bucket; this guarantees that getMinKey never returns an empty result when any keys remain. The high pointer is similarly adjusted when the last key of the current maximum count is removed, preserving the invariant that self.high always reflects the greatest count present.

Performance Optimizations

The design relies on constant-time set operations (add, discard) provided by Python’s built-in set type, allowing updates to the reverse mapping without linear scans. Maintaining self.high and self.low as direct references to the extreme count values eliminates the need to search through the self.classes dictionary for the maximum or minimum bucket during queries. The getMaxKey and getMinKey methods exploit the fact that iterating over a set yields an element in O(1) time, so they return a result after a single loop iteration. The only non-constant work occurs in the low adjustment loop after a decrement that empties the current minimum bucket; this loop progresses only until it encounters the next occupied count, which is typically a small number of steps because the structure tends to keep counts clustered. Overall, the combination of hash-based mappings, set containers, and cached extreme pointers yields an implementation that performs the core operations in constant amortized time.

Imagine a magical collection bin where toys go to be counted. There is a special book that keeps track of how many of each toy exists.

When a new toy is added, the book writes down that there is one. If a toy is already there, the book crosses out the old number and writes down a number that is one bigger. This is like moving a toy to a shelf labeled with its new count.

Sometimes toys are removed or the number is lowered. If a toy had three stickers on it and one is taken away, it moves back to the shelf where the toys with two stickers live. If a toy has no stickers left, it leaves the collection entirely.

There are two hidden helpers that keep watch over the shelves. One helper always keeps an eye on the highest shelf that has toys, and the other helper watches the lowest shelf that has toys. Because they are always watching, they can tell exactly which toys are the most popular and which ones are the loneliest whenever the request is made. If the shelves are empty, the helpers simply realize there is nothing to show.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python					Java	TS
	WalkCCC	C++	Python					Java
	leetcode.ca		Python					Java
	LeetcodeHelp	C++	Python					Java
	Progiez	C++	Python					Java
github	BigEggStudy				C#
	everthis			JS
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	martianoff					Scala
	ruoru						Rust
	suxrobGM				C#
	varunu28							Java
	wisdompeak	C++
	withaarzoo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
everthis	JavaScript
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality