All O`one Data Structure - Solution & Explanation

Problem Overview: Design a data structure that stores string keys with integer counts and supports four operations in constant time: inc, dec, getMaxKey, and getMinKey. Each increment or decrement changes a key's frequency, and you must always be able to retrieve any key with the maximum or minimum count in O(1) time.

Approach 1: Doubly Linked List with HashMap (O(1) time, O(n) space)

This approach maintains buckets of keys grouped by frequency using a doubly linked list. Each node in the list represents a specific count and stores a set of keys with that count. A HashMap maps each key to its corresponding bucket node. When you call inc or dec, the key moves to the adjacent bucket representing the updated frequency. If the target bucket does not exist, create it and insert it in the correct position in the list. Because bucket insertion, deletion, and key relocation are all constant-time operations, every API operation runs in O(1) time with O(n) space for storing keys. This design relies heavily on fast lookups from a hash table and constant-time insert/remove operations from a doubly-linked list.

Approach 2: Bucket with Key in Linked HashMap (O(1) time, O(n) space)

This variation also organizes keys by frequency buckets but uses maps to track relationships between counts and keys. A main map stores the current count for each key, while another structure maps each count to a set or ordered collection of keys. Incrementing a key moves it from one bucket to the next higher bucket; decrementing moves it to the previous bucket or removes it if the count reaches zero. Additional variables track the current minimum and maximum counts so getMinKey and getMaxKey return results instantly. The idea is similar to the linked list bucket approach but implemented using maps and sets instead of explicit node pointers. Hash lookups and set updates keep operations at O(1) average time with O(n) total space.

Recommended for interviews: Interviewers usually expect the doubly linked list bucket design. It demonstrates strong understanding of data structure design and how to combine hash maps with linked structures to maintain ordered frequency groups. A naive frequency map alone cannot return min and max keys in constant time. The bucketed linked list solves this by keeping counts sorted implicitly through neighbor pointers.