All O`one Data Structure

Link: https://leetcode.com/problems/all-oone-data-structure/description/

📖 Interpreting the Problem

Imagine you’re building a dynamic dictionary of strings where each string has an associated counter. Each time you “see” or “use” a string, its counter increases. If a string is no longer needed, its counter decreases. Occasionally, you’d like to ask: “Which string has the highest count right now?” or “Which has the lowest?”

This is exactly what the AllOne data structure needs to solve. It must support these operations:

• Increment the count of a string (add it if new)
• Decrement the count of a string (remove it if count hits zero)
• Return any string with the maximum count
• Return any string with the minimum count

And the real kicker? Every operation has to run in average O(1) time.

---

🧠 First Attempts and Their Pitfalls

When first approaching this problem, a natural idea is to use a hash map, where the keys are strings and the values are their counts. For incrementing or decrementing, this works beautifully in O(1). But trouble starts when we need to retrieve the minimum or maximum count key.

To obtain the key with the maximum count, you might consider scanning through all the entries and selecting the one with the highest value. That works… but only in O(N) time, where N is the number of keys. The same applies to achieving the minimum. So, while hash maps facilitate fast updates, they don’t aid in the retrieval of extremes quickly.

What about adding a priority queue to keep track of the max and min keys? That helps with retrieval, but makes updates expensive. Each update could take O(log N) to reorder the heap. We’re still not meeting the O(1) time constraint.

So clearly, we need a new idea that combines fast updates with instant min/max lookup.

---

💡 The Breakthrough Insight

The key realization is that the counts themselves can be used as a map. Instead of tracking keys directly, we track buckets of keys that all share the same count. If we have a way to jump quickly from one count bucket to the next higher or lower one, we can maintain instant access to both extremes.

Here’s the twist: we can simulate a doubly linked list of count buckets. Each bucket contains a set of strings with the same number of elements. When a key’s count changes, we move it to a different bucket. To find the minimum or maximum, we look at the first or last bucket.

But the given solution takes a slightly different, albeit clever approach: instead of using a traditional linked list, it uses two maps:

• d[count] stores the set of keys with that exact count (used for max lookups)
• r[count] also stores the set of keys, but helps manage the min index cleanly

In parallel, we track:

• count[key]: the current count for each string
• maxIndex and minIndexThe highest and lowest counts seen so far
• totalCount: total number of keys with non-zero counts

This hybrid design ensures that we can update counts, add or remove keys, and track extremes all in constant time.

📘 About HashMaps of Sets

Using unordered_map<int, unordered_set<string>> allows fast access to all keys with a particular count. Sets will enable us to insert and delete keys in constant time. This is crucial for quickly and efficiently transferring keys between buckets.

📘 Why maxIndex and minIndex Work

Instead of scanning the maps for the max or min, we store the current known maxIndex and minIndex and adjust them only when necessary. If the current max or min bucket becomes empty, we walk up or down the count space to find the next non-empty one.

---

🔍 Walking Through the Algorithm (with Examples)

Let’s consider a short sequence of operations to understand how the structure behaves.

AllOne obj;
obj.inc("apple");  // apple = 1
obj.inc("banana"); // banana = 1
obj.inc("apple");  // apple = 2

After these operations:

• count["apple"] = 2, in bucket 2
• count["banana"] = 1, in bucket 1
• maxIndex = 2, minIndex = 1
• getMaxKey() would return “apple”
• getMinKey() would return “banana”

Now, suppose that we decrease “apple”.

obj.dec("apple");  // apple = 1

Now both keys are in bucket 1. So maxIndex = minIndex = 1, and either key can be returned.

obj.dec("banana");  // banana removed

banana is gone, so only “apple” remains, with a count of 1. minIndex = 1, maxIndex = 1 again.

This illustrates how the data structure adapts as elements are added and removed from buckets.

---

📜 Pseudo Code

Initialize:
    count = empty map
    d = map from count to keys
    r = same as d (used for minIndex)
    maxIndex = 0, minIndex = 0, totalCount = 0

Function inc(key):
    Remove key from r[count[key]]
    Increase count[key] by 1
    Add key to d[count[key]] and r[count[key]]
    Update maxIndex and minIndex
    totalCount++

Function dec(key):
    Remove key from d[count[key]] and r[count[key]]
    Decrease count[key] by 1
    If count[key] > 0:
        Add key to r[count[key]]
        Update minIndex
    If d[maxIndex] is empty:
        maxIndex--
    If r[minIndex] is empty:
        minIndex-- or walk up to next count
    totalCount--

Function getMaxKey():
    Return any element from d[maxIndex] if exists

Function getMinKey():
    Return any element from r[minIndex] if exists

💻 Full Source Code with Rich Comments

class AllOne {
public:
    int maxIndex = 0, minIndex = 0;
    int totalCount = 0;
    unordered_map<int, unordered_set<string>> d; // For max lookup
    unordered_map<int, unordered_set<string>> r; // For min lookup
    unordered_map<string, int> count;            // Count of each key

    AllOne() {}

    void inc(string key) {
        r[count[key]].erase(key);                // Remove from old count bucket
        count[key]++;                            // Increase count
        d[count[key]].insert(key);               // Add to new max bucket
        r[count[key]].insert(key);               // Add to new min bucket
        maxIndex = max(maxIndex, count[key]);    // Update max if needed
        minIndex = min(minIndex, count[key]);    // Adjust min
        while (minIndex == 0 || r[minIndex].size() == 0) minIndex++; // Ensure valid min
        totalCount++;
    }

    void dec(string key) {
        d[count[key]].erase(key);                // Remove from max bucket
        r[count[key]].erase(key);                // Remove from min bucket
        count[key]--;                            // Decrease count

        if (count[key] > 0) {
            r[count[key]].insert(key);           // Reinsert if still positive
            minIndex = min(minIndex, count[key]);
        }

        if (d[maxIndex].empty()) maxIndex--;     // Adjust max index if needed
        if (r[minIndex].empty()) minIndex--;     // Adjust min index if needed

        totalCount--;

        if (minIndex == 0 && totalCount > 0) {
            while (minIndex == 0 || r[minIndex].empty()) minIndex++;
        }
    }

    string getMaxKey() {
        return totalCount == 0 ? "" : *d[maxIndex].begin();
    }

    string getMinKey() {
        return totalCount == 0 ? "" : *r[minIndex].begin();
    }
};

---

📌 Summary and Key Takeaways

The heart of this problem lies in managing count frequencies without sacrificing performance. By thinking in terms of buckets of equal counts, and maintaining direct access to those buckets via maps, we achieve what initially seems impossible: O(1) insert, delete, and min/max queries.

This is a classic example of how thinking in terms of grouped state (like frequency buckets) can unlock performance gains. The solution demonstrates that, with just hash maps and careful indexing, even the most complex constraints can be met.