432. All O`one Data Structure - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 * 10⁴ 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.

C++

```cpp
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <string>
using namespace std;

class AllOne {
public:
    AllOne() {
        bucketList.emplace_back(0);
        head = bucketList.begin();
    }
    void inc(string key) {
        if (!keyCountMap.count(key)) {
            keyCountMap[key] = head;
            head->keys.insert(key);
            moveForward(key);
        } else {
            moveForward(key);
        }
    }
    void dec(string key) {
        moveBackward(key);
    }
    string getMaxKey() {
        if (head->next == bucketList.end()) return "";
        return head->next->keys.empty() ? "" : *(head->next->keys.begin());
    }
    string getMinKey() {
        if (head->keys.empty()) return "";
        return *(head->keys.begin());
    }
private:
    struct Bucket {
        int count;
        unordered_set<string> keys;
        Bucket(int c) : count(c) {}
    };
    list<Bucket> bucketList;
    unordered_map<string, list<Bucket>::iterator> keyCountMap;
    list<Bucket>::iterator head;

    void moveForward(string key) {
        auto it = keyCountMap[key];
        auto itNext = it;
        ++itNext;
        if (itNext == bucketList.end() || itNext->count != it->count + 1) {
            auto insertIt = bucketList.insert(itNext, Bucket(it->count + 1));
            itNext = insertIt;
        }
        keyCountMap[key] = itNext;
        itNext->keys.insert(key);
        it->keys.erase(key);
        if (it->keys.empty() && it != head) {
            bucketList.erase(it);
        }
    }

    void moveBackward(string key) {
        auto it = keyCountMap[key];
        if (it != head) {
            auto itPrev = it;
            --itPrev;
            if (itPrev->count != it->count - 1) {
                auto insertIt = bucketList.insert(it, Bucket(it->count - 1));
                itPrev = insertIt;
            }
            keyCountMap[key] = itPrev;
            itPrev->keys.insert(key);
        } else {
            keyCountMap.erase(key);
        }
        it->keys.erase(key);
        if (it->keys.empty()) {
            bucketList.erase(it);
        }
    }
};
```

```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_KEY_LENGTH 11

// Node in doubly linked list
typedef struct Node {
    int count;
    struct Node *prev, *next;
    struct KeySet *keys;
} Node;

// Keys in the count node
typedef struct KeySet {
    char key[MAX_KEY_LENGTH];
    struct KeySet *next;
} KeySet;

// Hash map entry
typedef struct MapEntry {
    char key[MAX_KEY_LENGTH];
    Node *node;
} MapEntry;

// Hash map to store key and its count node
#define MAP_SIZE 1009
MapEntry *map[MAP_SIZE];

Node *head, *tail; // Head and tail of the doubly linked list

// Function definitions
Node *createNode(int count);
void removeKeyFromNode(Node *node, const char *key);
void addKeyToNode(Node *node, const char *key);
unsigned int hash(const char *key);
MapEntry* getMapEntry(const char *key);

Node *head, *tail; // Head and tail of the doubly linked list

unsigned int hash(const char *key) {
    unsigned int hash = 0;
    const char *ptr;
    for (ptr = key; *ptr != '\0'; ptr++) {
        hash = (hash * 31 + *ptr) % MAP_SIZE;
    }
    return hash;
}

MapEntry* getMapEntry(const char *key) {
    unsigned int h = hash(key);
    while (map[h] != NULL) {
        if (strcmp(map[h]->key, key) == 0) {
            return map[h];
        }
        h = (h + 1) % MAP_SIZE;
    }
    return NULL;
}

void inc(const char *key) {
    MapEntry *entry = getMapEntry(key);

    if (entry == NULL) {
        entry = (MapEntry *)malloc(sizeof(MapEntry));
        strcpy(entry->key, key);
        entry->node = head;
        addKeyToNode(head, key);

        unsigned int h = hash(key);
        while (map[h] != NULL) {
            h = (h + 1) % MAP_SIZE;
        }
        map[h] = entry;
    } else {
        Node *node = entry->node;
        removeKeyFromNode(node, key);
        Node *nextNode = node->next;

        if (nextNode == NULL || nextNode->count != node->count + 1) {
            Node *newNode = createNode(node->count + 1);
            newNode->prev = node;
            newNode->next = node->next;
            if (node->next != NULL) {
                node->next->prev = newNode;
            }
            node->next = newNode;
            nextNode = newNode;
        }

        addKeyToNode(nextNode, key);
        entry->node = nextNode;
    }
}

void dec(const char *key) {
    MapEntry *entry = getMapEntry(key);
    if (entry == NULL) {
        return;
    }

    Node *node = entry->node;
    removeKeyFromNode(node, key);

    if (node->count == 1) {
        free(entry);
        unsigned int h = hash(key);
        while (strcmp(map[h]->key, key) != 0) {
            h = (h + 1) % MAP_SIZE;
        }
        map[h] = NULL;
        return;
    }

    Node *prevNode = node->prev;

    if (prevNode == head || prevNode->count != node->count - 1) {
        Node *newNode = createNode(node->count - 1);
        newNode->prev = node->prev;
        newNode->next = node;
        node->prev->next = newNode;
        node->prev = newNode;
        prevNode = newNode;
    }

    addKeyToNode(prevNode, key);
    entry->node = prevNode;
}

Node *createNode(int count) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->count = count;
    node->prev = node->next = NULL;
    node->keys = NULL;
    return node;
}

void removeKeyFromNode(Node *node, const char *key) {
    KeySet *ks = node->keys, *prev = NULL;
    while (ks != NULL) {
        if (strcmp(ks->key, key) == 0) {
            if (prev == NULL) {
                node->keys = ks->next;
            } else {
                prev->next = ks->next;
            }
            free(ks);
            break;
        }
        prev = ks;
        ks = ks->next;
    }

    if (node->keys == NULL && (node->prev != NULL || node->next != NULL)) {
        node->prev->next = node->next;
        if (node->next != NULL) {
            node->next->prev = node->prev;
        }
        free(node);
    }
}

void addKeyToNode(Node *node, const char *key) {
    KeySet *ks = (KeySet *)malloc(sizeof(KeySet));
    strcpy(ks->key, key);
    ks->next = node->keys;
    node->keys = ks;
}

char* getMaxKey() {
    if (tail->prev == head) return "";

    return tail->prev->keys == NULL ? "" : tail->prev->keys->key;
}

char* getMinKey() {
    if (head->next == tail) return "";

    return head->next->keys == NULL ? "" : head->next->keys->key;
}

int main() {
    // Your code for testing the above logic (initializing head, tail, and running test cases)
    return 0;
}
```

This solution uses an unordered map to quickly access the element's frequency node in the key-count map. The solution maintains a list of buckets, where each bucket stores the keys with the same frequency. Increment or decrement operations effectively modify an element's position in this list with minimal searching, preserving O(1) complexity.

Complexity

Time Complexity: Each operation (inc, dec, getMaxKey, and getMinKey) is performed in O(1) average time due to the hash table backing.
Space Complexity: O(K) for storage space of keys and nodes in the data structure.

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.

Python

```python
class Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.prev = self.next = None

class AllOne:
    def __init__(self):
        self.key_count_map = {}
        self.head = Bucket(float('-inf'))
        self.tail = Bucket(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove_bucket(self, bucket):
        bucket.prev.next = bucket.next
        bucket.next.prev = bucket.prev

    def _add_bucket_after(self, new_bucket, prev_bucket):
        new_bucket.prev = prev_bucket
        new_bucket.next = prev_bucket.next
        prev_bucket.next.prev = new_bucket
        prev_bucket.next = new_bucket

    def inc(self, key):
        if key in self.key_count_map:
            bucket = self.key_count_map[key]
            next_bucket = bucket.next
            if next_bucket.count != bucket.count + 1:
                next_bucket = Bucket(bucket.count + 1)
                self._add_bucket_after(next_bucket, bucket)
            next_bucket.keys.add(key)
            self.key_count_map[key] = next_bucket
            bucket.keys.remove(key)
            if not bucket.keys:
                self._remove_bucket(bucket)
        else:
            if self.head.next.count != 1:
                self._add_bucket_after(Bucket(1), self.head)
            self.head.next.keys.add(key)
            self.key_count_map[key] = self.head.next

    def dec(self, key):
        bucket = self.key_count_map[key]
        bucket.keys.remove(key)
        if bucket.count == 1:
            del self.key_count_map[key]
        else:
            prev_bucket = bucket.prev
            if prev_bucket.count != bucket.count - 1:
                new_bucket = Bucket(bucket.count - 1)
                self._add_bucket_after(new_bucket, prev_bucket)
                prev_bucket = new_bucket
            prev_bucket.keys.add(key)
            self.key_count_map[key] = prev_bucket
        if not bucket.keys:
            self._remove_bucket(bucket)

    def getMaxKey(self):
        return '' if self.tail.prev == self.head else next(iter(self.tail.prev.keys))

    def getMinKey(self):
        return '' if self.head.next == self.tail else next(iter(self.head.next.keys))
```

Java

```java
import java.util.*;

class AllOne {
    private class Bucket {
        int count;
        Set<String> keys;
        Bucket prev, next;

        Bucket(int count) {
            this.count = count;
            this.keys = new HashSet<>();
        }
    }

    private Map<String, Bucket> keyToBucketMap;
    private Bucket head, tail;

    public AllOne() {
        keyToBucketMap = new HashMap<>();
        head = new Bucket(Integer.MAX_VALUE);
        tail = new Bucket(Integer.MIN_VALUE);
        head.next = tail;
        tail.prev = head;
    }

    public void inc(String key) {
        if (!keyToBucketMap.containsKey(key)) {
            if (tail.prev.count != 1) addBucketAfter(new Bucket(1), tail.prev);
            tail.prev.keys.add(key);
            keyToBucketMap.put(key, tail.prev);
        } else {
            Bucket bucket = keyToBucketMap.get(key);
            Bucket next = bucket.next;
            if (next == null || next.count != bucket.count + 1) next = addBucketAfter(new Bucket(bucket.count + 1), bucket);
            next.keys.add(key);
            keyToBucketMap.put(key, next);
            bucket.keys.remove(key);
            if (bucket.keys.isEmpty()) removeBucket(bucket);
        }
    }

    public void dec(String key) {
        Bucket bucket = keyToBucketMap.get(key);
        if (bucket == null) return;
        if (bucket.count == 1) {
            keyToBucketMap.remove(key);
            bucket.keys.remove(key);
            if (bucket.keys.isEmpty()) removeBucket(bucket);
        } else {
            Bucket prev = bucket.prev;
            if (prev == head || prev.count != bucket.count - 1) prev = addBucketAfter(new Bucket(bucket.count - 1), bucket.prev);
            prev.keys.add(key);
            keyToBucketMap.put(key, prev);
            bucket.keys.remove(key);
            if (bucket.keys.isEmpty()) removeBucket(bucket);
        }
    }

    private Bucket addBucketAfter(Bucket newBucket, Bucket prevBucket) {
        newBucket.prev = prevBucket;
        newBucket.next = prevBucket.next;
        prevBucket.next.prev = newBucket;
        prevBucket.next = newBucket;
        return newBucket;
    }

    private void removeBucket(Bucket bucket) {
        bucket.prev.next = bucket.next;
        bucket.next.prev = bucket.prev;
    }

    public String getMaxKey() {
        return head.next == tail ? "" : head.next.keys.iterator().next();
    }

    public String getMinKey() {
        return tail.prev == head ? "" : tail.prev.keys.iterator().next();
    }
}
```

In this Python implementation, a hash map associates keys with their buckets and enables constant-time access to any key's current count. The buckets themselves form a doubly linked list with nodes that represent possible key counts. The operations maintain constant-time complexity by operating primarily within these local bucket objects.

Complexity

Time Complexity: O(1) average time for each operation due to efficient space and structure handling.
Space Complexity: O(K) space used by the keys and buckets, given K unique keys.

Try this approach in the editor

Complexity comparison

Approach	Complexity
Doubly Linked List with HashMap	Time Complexity: Each operation (inc, dec, getMaxKey, and getMinKey) is performed in O(1) average time due to the hash table backing. Space Complexity: O(K) for storage space of keys and nodes in the data structure.
Bucket with Key in Linked HashMap	Time Complexity: O(1) average time for each operation due to efficient space and structure handling. Space Complexity: O(K) space used by the keys and buckets, given K unique keys.

Complexity analysis

Approach	Time	Space	When to Use
Doubly Linked List with HashMap	O(1) for all operations	O(n)	Best general solution for interviews and production. Maintains ordered frequency buckets efficiently.
Bucket Map with Key Sets	O(1) average	O(n)	Useful in languages with strong map/set support like Python or Java where managing explicit linked nodes is unnecessary.

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.

All O`one Data Structure solution and explanation

The problem

Approach overview

Approach 1: Doubly Linked List with HashMap

Approach 2: Bucket with Key in Linked HashMap

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

All O`one Data Structure solution and explanation

The problem

Approach overview

Approach 1: Doubly Linked List with HashMap

Approach 2: Bucket with Key in Linked HashMap

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems