LeetCode 432 - All O`one Data Structure

LeetCode Problem 432

Difficulty: 🔴 Hard
Topics: Hash Table, Linked List, Design, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to design a special data structure that stores string keys together with their occurrence counts. The structure must support incrementing and decrementing counts, while also being able to instantly retrieve one key with the maximum count and one key with the minimum count.

Unlike ordinary frequency counting problems, this problem imposes a strict performance requirement. Every operation must run in average O(1) time complexity. This means we cannot scan all keys whenever we need the minimum or maximum count.

The operations behave as follows:

• inc(key) increases the frequency of key by one.
• If the key does not already exist, it should be inserted with count 1.
• dec(key) decreases the frequency of key by one.
• If the frequency becomes 0, the key must be removed entirely.
• getMaxKey() returns any key with the highest frequency.
• getMinKey() returns any key with the lowest frequency.

The input in LeetCode is represented as a sequence of operations and parameters. The output contains the return value for each operation that produces one.

The constraints are important because they eliminate many simpler approaches:

• Up to 5 * 10^4 operations can occur.
• Every operation must be efficient.
• Keys are short lowercase strings.
• The problem guarantees that dec() is only called on existing keys.

The hardest part of this problem is maintaining both minimum and maximum frequencies dynamically while supporting constant-time updates.

Several edge cases are especially important:

• Incrementing a completely new key.
• Decrementing a key whose count becomes zero.
• Maintaining correct min and max after removing the last key in a frequency bucket.
• Handling multiple keys with the same frequency.
• Returning an empty string when the structure becomes empty.

A naive implementation can easily become inefficient or inconsistent when frequencies change frequently.

Approaches

Brute Force Approach

The most straightforward solution is to use a hash map from key to count.

Whenever inc() or dec() is called, we simply update the count in the map. Then, when getMaxKey() or getMinKey() is called, we scan through every key in the hash map to find the maximum or minimum count.

This approach is correct because the map always stores the latest count for every key. A full scan guarantees we find the proper minimum or maximum.

However, this approach is too slow because scanning all keys requires O(n) time, where n is the number of distinct keys. Since up to 5 * 10^4 operations may occur, repeated scans can lead to quadratic behavior in the worst case.

Optimal Approach

The key insight is that we need direct access to both the smallest and largest frequency groups at all times.

Instead of storing only individual key counts, we group keys by frequency. We maintain:

• A doubly linked list of frequency buckets.

• Each bucket stores:

• A frequency count.

• A set of keys with that frequency.

• A hash map from key to its current bucket.

The linked list is ordered by frequency from smallest to largest. Because of this ordering:

• The first real bucket always contains the minimum frequency.
• The last real bucket always contains the maximum frequency.

When a key changes frequency, we move it between neighboring buckets in constant time.

This design works because frequencies only ever change by +1 or -1, meaning a key only moves to an adjacent bucket.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per query	O(n)	Scan all keys to find min/max
Optimal	O(1) average per operation	O(n)	Doubly linked list of frequency buckets

Algorithm Walkthrough

Data Structures

We use three core components:

• A doubly linked list of buckets ordered by frequency.
• A hash map from key to bucket node.
• A set inside each bucket storing all keys with that frequency.

Each bucket node contains:

• count
• keys
• prev
• next

We also use dummy head and tail nodes to simplify insertion and deletion logic.

Step-by-Step Algorithm

1. Initialize the linked list with dummy head and tail nodes.

The head represents values smaller than all valid counts, and the tail represents values larger than all valid counts. This eliminates edge-case checks when inserting or removing buckets. 2. Maintain a hash map from key to bucket node.

This allows constant-time lookup of a key's current frequency bucket. 3. Handle inc(key) for a new key.

If the key does not exist:

• Check whether the first real bucket has count 1.
• If not, create a new bucket with count 1.
• Insert the key into that bucket.
• Store the mapping from key to bucket.

4. Handle inc(key) for an existing key.

• Locate the current bucket using the hash map.
• Determine the target frequency, which is current_count + 1.
• Check whether the next bucket already has that frequency.
• If not, create a new bucket and insert it after the current bucket.
• Move the key into the new bucket.
• Remove the key from the old bucket.
• If the old bucket becomes empty, remove it from the linked list.

5. Handle dec(key).

• Locate the current bucket.

• If the current count is 1, remove the key entirely from the hash map.

• Otherwise:

• Determine the target frequency, which is current_count - 1.

• Check whether the previous bucket already has that frequency.

• If not, create a new bucket and insert it before the current bucket.

• Move the key into the target bucket.

• Update the hash map.

• Remove the key from the old bucket.

• If the old bucket becomes empty, remove it from the linked list.

6. Handle getMaxKey().

The maximum frequency bucket is immediately before the tail dummy node. Return any key from that bucket. 7. Handle getMinKey().

The minimum frequency bucket is immediately after the head dummy node. Return any key from that bucket.

Why it works

The linked list always remains sorted by frequency. Every key resides in exactly one bucket representing its current count. Since frequencies only change by one at a time, keys only move between adjacent buckets. The head and tail neighbors therefore always represent the minimum and maximum frequencies. Every update modifies only local structures, which guarantees constant average time complexity.

Python Solution

class Node:
    def __init__(self, count: int):
        self.count = count
        self.keys = set()
        self.prev = None
        self.next = None

class AllOne:

    def __init__(self):
        self.head = Node(0)
        self.tail = Node(0)

        self.head.next = self.tail
        self.tail.prev = self.head

        self.key_to_node = {}

    def _insert_after(self, node: Node, new_node: Node) -> None:
        new_node.prev = node
        new_node.next = node.next

        node.next.prev = new_node
        node.next = new_node

    def _remove_node(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def inc(self, key: str) -> None:
        if key not in self.key_to_node:
            if self.head.next != self.tail and self.head.next.count == 1:
                node = self.head.next
            else:
                node = Node(1)
                self._insert_after(self.head, node)

            node.keys.add(key)
            self.key_to_node[key] = node

        else:
            current = self.key_to_node[key]
            next_count = current.count + 1

            if current.next != self.tail and current.next.count == next_count:
                next_node = current.next
            else:
                next_node = Node(next_count)
                self._insert_after(current, next_node)

            next_node.keys.add(key)
            self.key_to_node[key] = next_node

            current.keys.remove(key)

            if not current.keys:
                self._remove_node(current)

    def dec(self, key: str) -> None:
        current = self.key_to_node[key]

        if current.count == 1:
            del self.key_to_node[key]
        else:
            prev_count = current.count - 1

            if current.prev != self.head and current.prev.count == prev_count:
                prev_node = current.prev
            else:
                prev_node = Node(prev_count)
                self._insert_after(current.prev, prev_node)

            prev_node.keys.add(key)
            self.key_to_node[key] = prev_node

        current.keys.remove(key)

        if not current.keys:
            self._remove_node(current)

    def getMaxKey(self) -> str:
        if self.tail.prev == self.head:
            return ""

        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        if self.head.next == self.tail:
            return ""

        return next(iter(self.head.next.keys))

# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()

The implementation begins by defining a Node class representing a frequency bucket. Each node stores a count and a set of keys that currently share that count.

The AllOne class maintains dummy head and tail nodes to simplify linked list manipulation. This prevents special-case logic when inserting at the beginning or end.

The helper method _insert_after() inserts a new bucket directly after a given node. The _remove_node() helper removes an empty bucket from the linked list.

The inc() method handles two situations. For new keys, it either reuses an existing frequency-1 bucket or creates one. For existing keys, it moves the key into the next frequency bucket, creating that bucket if necessary.

The dec() method mirrors this logic in reverse. Keys with count 1 are removed entirely. Otherwise, they move into the previous frequency bucket.

The getMaxKey() and getMinKey() methods are extremely efficient because the linked list is always sorted by frequency. The maximum bucket is always adjacent to the tail, and the minimum bucket is always adjacent to the head.

Go Solution

package main

type Node struct {
	count int
	keys  map[string]bool
	prev  *Node
	next  *Node
}

type AllOne struct {
	head      *Node
	tail      *Node
	keyToNode map[string]*Node
}

func Constructor() AllOne {
	head := &Node{
		keys: make(map[string]bool),
	}

	tail := &Node{
		keys: make(map[string]bool),
	}

	head.next = tail
	tail.prev = head

	return AllOne{
		head:      head,
		tail:      tail,
		keyToNode: make(map[string]*Node),
	}
}

func (this *AllOne) insertAfter(node *Node, newNode *Node) {
	newNode.prev = node
	newNode.next = node.next

	node.next.prev = newNode
	node.next = newNode
}

func (this *AllOne) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *AllOne) Inc(key string) {
	if current, exists := this.keyToNode[key]; !exists {

		var node *Node

		if this.head.next != this.tail && this.head.next.count == 1 {
			node = this.head.next
		} else {
			node = &Node{
				count: 1,
				keys:  make(map[string]bool),
			}
			this.insertAfter(this.head, node)
		}

		node.keys[key] = true
		this.keyToNode[key] = node

	} else {

		nextCount := current.count + 1

		var nextNode *Node

		if current.next != this.tail && current.next.count == nextCount {
			nextNode = current.next
		} else {
			nextNode = &Node{
				count: nextCount,
				keys:  make(map[string]bool),
			}
			this.insertAfter(current, nextNode)
		}

		nextNode.keys[key] = true
		this.keyToNode[key] = nextNode

		delete(current.keys, key)

		if len(current.keys) == 0 {
			this.removeNode(current)
		}
	}
}

func (this *AllOne) Dec(key string) {
	current := this.keyToNode[key]

	if current.count == 1 {
		delete(this.keyToNode, key)
	} else {

		prevCount := current.count - 1

		var prevNode *Node

		if current.prev != this.head && current.prev.count == prevCount {
			prevNode = current.prev
		} else {
			prevNode = &Node{
				count: prevCount,
				keys:  make(map[string]bool),
			}
			this.insertAfter(current.prev, prevNode)
		}

		prevNode.keys[key] = true
		this.keyToNode[key] = prevNode
	}

	delete(current.keys, key)

	if len(current.keys) == 0 {
		this.removeNode(current)
	}
}

func (this *AllOne) GetMaxKey() string {
	if this.tail.prev == this.head {
		return ""
	}

	for key := range this.tail.prev.keys {
		return key
	}

	return ""
}

func (this *AllOne) GetMinKey() string {
	if this.head.next == this.tail {
		return ""
	}

	for key := range this.head.next.keys {
		return key
	}

	return ""
}

/**
 * Your AllOne object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Inc(key);
 * obj.Dec(key);
 * param_3 := obj.GetMaxKey();
 * param_4 := obj.GetMinKey();
 */

The Go implementation follows the same design as the Python version, but there are some language-specific differences.

Go does not have a built-in set type, so we simulate sets using map[string]bool.

Instead of Python's dynamic references, Go uses pointers explicitly for linked list nodes.

When retrieving a key from a bucket, Go iterates over the map and immediately returns the first key encountered.

Memory management is handled automatically by Go's garbage collector, so removed nodes do not require explicit deallocation.

Worked Examples

Example 1

Operations:

["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Step-by-Step Trace

Operation	Linked List State	Result
Initialize	Empty
inc("hello")	1:{hello}
inc("hello")	2:{hello}
getMaxKey()	2:{hello}	"hello"
getMinKey()	2:{hello}	"hello"
inc("leet")	1:{leet} <-> 2:{hello}
getMaxKey()	1:{leet} <-> 2:{hello}	"hello"
getMinKey()	1:{leet} <-> 2:{hello}	"leet"

After the third increment, "hello" has frequency 2 while "leet" has frequency 1. Because the linked list is sorted by count, the minimum bucket appears first and the maximum bucket appears last.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) average	Every operation performs only hash map lookups and local linked list updates
Space	O(n)	We store all keys and frequency buckets

The key reason the solution achieves constant average time complexity is that keys only move between adjacent frequency buckets. We never scan the entire structure. Hash maps provide constant-time lookup, while the doubly linked list provides constant-time insertion and removal of buckets.

Test Cases

# Example case
obj = AllOne()
obj.inc("hello")
obj.inc("hello")
assert obj.getMaxKey() == "hello"  # single max key
assert obj.getMinKey() == "hello"  # single min key

obj.inc("leet")
assert obj.getMaxKey() == "hello"  # hello has count 2
assert obj.getMinKey() == "leet"   # leet has count 1

# Removing a key completely
obj = AllOne()
obj.inc("a")
obj.dec("a")
assert obj.getMaxKey() == ""  # structure empty
assert obj.getMinKey() == ""  # structure empty

# Multiple keys same frequency
obj = AllOne()
obj.inc("a")
obj.inc("b")

assert obj.getMaxKey() in {"a", "b"}  # both valid
assert obj.getMinKey() in {"a", "b"}  # both valid

# Frequency increase ordering
obj = AllOne()
obj.inc("a")
obj.inc("b")
obj.inc("b")

assert obj.getMaxKey() == "b"  # b count is 2
assert obj.getMinKey() == "a"  # a count is 1

# Frequency decrease ordering
obj = AllOne()
obj.inc("x")
obj.inc("x")
obj.inc("y")

obj.dec("x")

assert obj.getMaxKey() in {"x", "y"}  # both count 1
assert obj.getMinKey() in {"x", "y"}  # both count 1

# Stress bucket creation/removal
obj = AllOne()

for _ in range(5):
    obj.inc("z")

for _ in range(4):
    obj.dec("z")

assert obj.getMaxKey() == "z"  # remaining count 1
assert obj.getMinKey() == "z"  # remaining count 1

obj.dec("z")

assert obj.getMaxKey() == ""  # empty after deletion
assert obj.getMinKey() == ""  # empty after deletion

Test	Why
Basic example	Validates normal operation
Remove last key	Ensures empty structure handled correctly
Multiple equal frequencies	Confirms any valid key may be returned
Increment ordering	Verifies max tracking
Decrement ordering	Verifies bucket movement downward
Bucket cleanup stress	Ensures empty buckets are removed properly

Edge Cases

One important edge case occurs when decrementing a key whose count becomes zero. This is a common source of bugs because the key must be removed both from its bucket and from the global hash map. If the bucket also becomes empty, the bucket itself must be removed from the linked list. The implementation handles this by first updating or deleting the key mapping, then removing the key from the bucket, and finally deleting the bucket if necessary.

Another tricky situation occurs when inserting a completely new key. If no frequency-1 bucket exists, a new bucket must be inserted directly after the head node. Failing to maintain sorted order here would break getMinKey(). The implementation explicitly checks whether the first real bucket already has count 1 before deciding to create a new bucket.

A third edge case happens when multiple keys share the same frequency. A naive implementation might accidentally create duplicate buckets with the same count. This implementation avoids that by always checking neighboring buckets before creating a new one. Since frequencies only change by one, the correct destination bucket can only be adjacent to the current bucket.

A final important case is when the structure becomes empty. Both getMaxKey() and getMinKey() must return an empty string instead of causing an error. The dummy head and tail nodes make this check straightforward because an empty structure always satisfies head.next == tail.