All O'one Data Structure
Understanding the Problem
We need to build a data structure that tracks how many times each string has been incremented and, at any moment, can return a string with the highest count and one with the lowest, all in O(1) time.
A hash map covers the count updates: incrementing and decrementing are constant-time map operations. Finding the min and max in O(1) is the hard part. A heap gives O(log n) insert and delete. A balanced tree needs O(log n) for rebalancing. Neither meets the requirement.
Full sorting is unnecessary, though. Only the minimum and maximum matter, and a count changes by exactly 1 per operation. When a key's count goes from c to c+1, the key moves to the neighboring position in count order; nothing else shifts. That property is what makes O(1) possible.
Key Constraints:
At most 5 * 10^4 calls-- The cost that matters is per call. The problem requires O(1) average time per operation, which rules out heaps and balanced trees at O(log n).key consists of lowercase English letters-- Keys are regular strings, no special handling needed.dec is only called on existing keys-- We don't need to handle decrementing a non-existent key.
Approach 1: Brute Force with Hash Map
Intuition
Store each key's count in a hash map. Incrementing and decrementing are O(1) map updates. For getMaxKey and getMinKey, scan all entries and return the key with the highest or lowest count.
This is correct, but every getMaxKey or getMinKey call costs O(n), which violates the O(1) requirement. It still serves as a baseline: the map already answers count updates in O(1), so the min/max query is the only operation left to fix.
Algorithm
- Maintain a hash map
countsthat maps each key to its integer count. - For
inc(key): incrementcounts[key]by 1. If the key doesn't exist, set it to 1. - For
dec(key): decrementcounts[key]by 1. If it reaches 0, remove the key. - For
getMaxKey(): iterate through all entries in the map and return the key with the highest count. Return""if the map is empty. - For
getMinKey(): iterate through all entries and return the key with the lowest count. Return""if the map is empty.
Example Walkthrough
Input:
After inc("hello"), inc("hello"), the map holds one entry:
getMaxKey() scans the map and finds "hello" with count 2. getMinKey() also returns "hello" since it is the only key.
After inc("leet"), the map gains a second entry:
getMaxKey() scans and returns "hello" (count 2). getMinKey() scans and returns "leet" (count 1). The returned sequence matches the expected output: [null, null, null, "hello", "hello", null, "hello", "leet"]. Each scan visited every entry, which is the cost the next approach removes.
Code
- Time Complexity: O(1) for
incanddec, O(n) forgetMaxKeyandgetMinKey. Hash map operations are O(1), but finding min/max requires scanning all n keys. - Space Complexity: O(n). One hash map entry per unique key.
Every call to getMaxKey or getMinKey scans the entire hash map, recomputing the answer from scratch even though the last inc or dec changed one key's count by 1. The next approach keeps keys grouped by count in sorted order, so the current min and max always sit at the two ends of a list.
Approach 2: Doubly-Linked List of Count Buckets (Optimal)
Intuition
A count moves from c to c+1 or from c to c-1, never anywhere else. A fully sorted structure is overkill; a key only ever needs to move between adjacent "count buckets."
The structure is a doubly-linked list where each node represents one count value and holds the set of keys that currently have that count. The list stays sorted by count, smallest at the head and largest at the tail. getMinKey reads the node next to the head, getMaxKey reads the node next to the tail, both O(1).
Incrementing a key from count c to c+1 removes it from bucket c and adds it to bucket c+1. If bucket c+1 does not exist, we create a new node right after bucket c, an O(1) insertion in a doubly-linked list. If bucket c becomes empty after the removal, we splice that node out, also O(1).
A hash map from each key to its bucket node locates the key's current bucket without searching. Every operation is then a hash map lookup plus an O(1) list splice plus an O(1) set update.
The list stays sorted by count even though no operation ever compares more than two neighbors. Assume the list is sorted before an operation. When a key moves from bucket c to c+1 and no c+1 bucket exists, the node after bucket c holds a count greater than c (sorted order) and not equal to c+1 (the code checked), so it is at least c+2. Inserting the new c+1 bucket directly after bucket c therefore preserves the order. The symmetric argument covers dec, which inserts a c-1 bucket directly before bucket c. The sentinels (count 0 at the head, infinity at the tail) guarantee every real bucket has a neighbor on both sides, so the same insertion logic works at the ends of the list.
Algorithm
- Create a doubly-linked list with sentinel head and tail nodes (count 0 and infinity). This avoids null checks.
- Maintain a hash map
keyToNodethat maps each key to its current bucket node in the linked list. - For
inc(key): - If the key is new, check if the node right after the head has count 1. If so, add the key to that node's set. Otherwise, create a new node with count 1 and insert it right after the head.
- If the key exists in node
curr(count c), move it to a node with count c+1. If the next node has count c+1, add the key there. Otherwise, create a new node with count c+1 and insert it right aftercurr. - Remove the key from its old node. If that node's set becomes empty, remove it from the linked list.
- For
dec(key): - Find the key's current node
curr(count c). - If c == 1, remove the key entirely (from both the node and the hash map).
- Otherwise, move it to a node with count c-1. If the previous node has count c-1, add the key there. Otherwise, create a new node with count c-1 and insert it right before
curr. - Remove the key from its old node. If that node becomes empty, remove it from the linked list.
- For
getMaxKey(): return any key from the node right before the tail sentinel. - For
getMinKey(): return any key from the node right after the head sentinel.
Example Walkthrough
The trace starts with the operations from Example 1: two increments of "hello", min/max queries, an increment of "leet", and two more queries. Two dec("hello") calls follow, showing the two decrement cases: moving a key into an existing neighbor bucket and removing a key whose count reaches 0.
Through the Example 1 portion, the queries return "hello", "hello", then "hello" and "leet", matching the expected output. No step touched more than two list nodes: every inc and dec works on the key's current bucket and one neighbor, and every query reads a single node next to a sentinel.
Code
- Time Complexity: O(1) for all operations.
incanddeceach do a hash map lookup O(1), linked list insert/delete O(1), and set add/remove O(1).getMaxKeyaccesses tail.prev and gets any element from its set, O(1).getMinKeyaccesses head.next similarly, O(1). - Space Complexity: O(n), where n is the number of unique keys. The hash map stores n entries. The linked list has at most n nodes (one per distinct count value). Each key appears in exactly one bucket's set.