Skip to main content
Talentd

All O`one Data Structure - Solution & Explanation

HardHash TableLinked ListDesignDoubly-Linked List14 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

Problem Statement

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

  • AllOne() Initializes the object of the data structure.
  • inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
  • dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
  • getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
  • getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

 

Example 1:

Input
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output
[null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"

 

Constraints:

  • 1 <= key.length <= 10
  • key consists of lowercase English letters.
  • It is guaranteed that for each call to dec, key is existing in the data structure.
  • At most 5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

Approach Overview

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.

Approach 1: Doubly Linked List with HashMap

This approach involves using a hash map to store the frequency of each key and a doubly linked list (DLL) to keep track of the keys at each frequency level. Each node in the DLL represents a unique frequency and holds a set of keys that have the same frequency. This data structure allows us to efficiently update, delete, and access keys while keeping track of the frequencies.

The solution uses a doubly linked list to store nodes that keep track of key counts, while a hash map points to these nodes for quick updates. Each node's key set is a linked list storing the keys currently having a particular count. When counts are incremented or decremented, keys are moved to adjacent count nodes, ensuring efficient access for getMaxKey and getMinKey.

Code

CC++

C

C++

Complexity

Time Complexity: Each of the operations—inc, dec, getMaxKey, and getMinKey—takes O(1) on average.
Space Complexity: O(K) for storing the keys and their corresponding nodes, where K is the number of unique keys.

Try this approach in the editor →

Approach 2: Bucket with Key in Linked HashMap

This approach utilizes a linked hash map where the keys are linked, ensuring a constant-time access. Frequencies are stored in hash maps that maintain the order of the elements. Keys are moved forward and backward among buckets when incrementing and decrementing, respectively. This combination allows the solution to be optimal with respect to speed and space.

This Java implementation leverages a doubly linked list of buckets, where each bucket holds keys with the same frequency. The frequency is managed by the bucket list, enabling constant-time updates. Each operation (inc, dec, getMaxKey, and getMinKey) requires only local adjustments within a bucket, which makes this structure efficient and fast.

Code

JavaPython

Java

Python

Complexity

Time Complexity: Each operation incurs only O(1) time on average due to the hash map use.
Space Complexity: O(K) in terms of storage for keys and nodes, where K is the number of unique keys.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJava

Python

Java

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Doubly Linked List with HashMap

Time Complexity: Each of the operations—inc, dec, getMaxKey, and getMinKey—takes O(1) on average.
Space Complexity: O(K) for storing the keys and their corresponding nodes, where K is the number of unique keys.

Bucket with Key in Linked HashMap

Time Complexity: Each operation incurs only O(1) time on average due to the hash map use.
Space Complexity: O(K) in terms of storage for keys and nodes, where K is the number of unique keys.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Doubly Linked List with HashMapO(1) for all operationsO(n)Best general solution for interviews and production. Maintains ordered frequency buckets efficiently.
Bucket Map with Key SetsO(1) averageO(n)Useful in languages with strong map/set support like Python or Java where managing explicit linked nodes is unnecessary.

Video Solution

All O`one Data Structure | Super Simple Explanation | Leetcode 432 | codestorywithMIK • codestorywithMIK • 11,537 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is All O`one Data Structure easy or hard?
All O`one Data Structure is classified as a Hard problem because it requires designing a custom data structure that guarantees O(1) operations for multiple updates and queries. The challenge comes from maintaining both minimum and maximum frequencies efficiently while keys constantly change counts.
How to solve All O`one Data Structure in O(1)?
Store each frequency in a bucket node of a doubly linked list. Maintain a hash map from key to its bucket. When incrementing or decrementing a key, move it to the neighboring bucket representing the new count, creating or removing buckets when needed. The head and tail of the list always provide the minimum and maximum keys.
All O`one Data Structure Python or Java solution
Python and Java solutions typically use dictionaries or hash maps to track key counts and map counts to sets of keys. Some implementations simulate bucket nodes using maps and linked structures. The optimal implementations still maintain O(1) average time for all operations.
What is the best approach for All O`one Data Structure?
The optimal approach uses a doubly linked list of frequency buckets combined with a hash map mapping keys to their bucket nodes. Each bucket stores keys with the same count. Increment and decrement operations move keys between adjacent buckets, keeping every operation including getMaxKey and getMinKey in O(1) time.
Is All O`one Data Structure asked at Google/Amazon/Meta?
All O`one Data Structure is a classic hard-level design problem frequently associated with top-tier companies such as Google, Meta, and Amazon. It tests understanding of hash maps, linked lists, and constant-time data structure design under strict performance constraints.
What data structure is used in All O`one Data Structure?
The core design combines a hash table with a doubly linked list of frequency buckets. The hash table provides O(1) lookup for each key, while the linked list maintains counts in sorted order so the minimum and maximum frequencies are always accessible instantly.
What is the time complexity of All O`one Data Structure?
The designed data structure must support inc, dec, getMaxKey, and getMinKey in O(1) time. Using a hash map for key lookup and a doubly linked list of frequency buckets allows constant-time insertion, deletion, and movement of keys between frequency groups.

Ready to solve this problem?

Practice All O`one Data Structure with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters