Coding Interview PatternsAll O(1) Data Structure
HardCustom Data Structures

All O(1) Data Structure

Explanation & Solution

Practice Problem

Description

Design a data structure that supports incrementing/decrementing string counts and retrieving the key with the max or min count, all in O(1) time.

Implement a function that processes an array of operations and an array of arguments:

  • "AllOne" — Initializes the data structure.
  • "inc" — Increments the count of string key by 1. If key doesn't exist, insert it with count 1.
  • "dec" — Decrements the count of string key by 1. If the count reaches 0, remove key.
  • "getMaxKey" — Returns one of the keys with the maximum count. If no keys exist, return "".
  • "getMinKey" — Returns one of the keys with the minimum count. If no keys exist, return "".
Input:operations = ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"], args = [[],["hello"],["hello"],[],[],["leet"],[],[]]
0
AllOne
1
inc
2
inc
3
getMaxKey
4
getMinKey
5
inc
6
getMaxKey
7
getMinKey
Output:[null,null,null,"hello","hello",null,"hello","leet"]
0
null
1
null
2
null
3
hello
4
hello
5
null
6
hello
7
leet

Explanation: inc(hello)→count 1. inc(hello)→count 2. max=min=hello. inc(leet)→count 1. max=hello(2), min=leet(1).

Constraints

  • 1 <= key.length <= 10
  • key consists of lowercase English letters
  • It is guaranteed that dec is never called on a key with count 0
  • At most 5 * 10^4 calls to inc, dec, getMaxKey, and getMinKey

Approach

Custom Data Structures pattern

1. Doubly Linked List + Hash Map

  • The DLL has nodes sorted by count from smallest (near head) to largest (near tail)
  • Each node holds a count and a Map of keys at that count
  • keyNode maps each key to its current DLL node for O(1) lookup
  • Dummy head (count=0) and tail (count=∞) simplify edge cases

2. Implement Inc

  • If key exists: its current node's count + 1 should be the next node
  • If the next node doesn't have that count, insert a new node between current and next
  • Move the key to the next node, remove from current, delete current node if empty
  • If key is new: move to the node with count=1, creating it after head if needed

3. Implement Dec

  • If count - 1 = 0, simply remove the key entirely
  • Otherwise: find or create a node with count - 1 before the current node
  • Move the key there, clean up the current node if empty

4. GetMaxKey and GetMinKey

  • Max: return any key from tail.prev (the node with the highest count)
  • Min: return any key from head.next (the node with the lowest count)
  • Both are O(1) since the DLL maintains sorted order

Key Insight

  • The DLL maintains a sorted-by-count structure without sorting — each inc/dec only touches adjacent nodes
  • Using a Map (ordered by insertion) inside each node provides a consistent key to return
Time
O(1) for all operations
Space
O(n) where n is the number of unique keys

Solution Code

Previous
LFU Cache
Next
Insert Delete GetRandom O(1) - Duplicates Allowed