Maximum Frequency Stack

How it works

Instead of using a hash map for frequency-indexed stacks, we can use a dynamic array (list). The index in the array represents the frequency level. When an element reaches a new frequency, we extend the array if needed. The last non-empty stack in the array always corresponds to the maximum frequency, eliminating the need to track maxCnt separately.

Steps

1. Initialize a frequency hash map cnt and a list stacks with an empty placeholder at index 0 (since frequencies start at 1).
2. For push(val): increment the value's count. If this count equals the current length of stacks, append a new empty stack. Push the value onto the stack at index equal to its frequency.
3. For pop(): pop from the last stack in the list, decrement that value's frequency. If the last stack becomes empty, remove it from the list. Return the popped value.

Complexity

• Time complexity:
  • O(1) time for each push() function call.
  • O(1) time for each pop() function call.
• Space complexity: O(n)

Where n is the number of elements in the stack.

Things to watch for

Breaking Ties Incorrectly

When multiple elements share the highest frequency, the most recently pushed one must be popped first. A common mistake is to pop an arbitrary element with the maximum frequency, or to pop the first occurrence instead of the last. The heap solution handles this by storing insertion order as a secondary sort key; the stack-of-stacks solution naturally maintains recency by using stack ordering within each frequency level.

Not Decrementing Frequency After Pop

After popping an element, its frequency count must be decremented. Forgetting this step causes the data structure to believe the element still occurs at its previous frequency, leading to incorrect behavior on subsequent operations. Both the frequency map and any frequency-indexed structures must be updated consistently.

Mismanaging the Maximum Frequency Tracker

The stack-of-stacks approach tracks maxCnt to know which stack to pop from. A subtle bug occurs when the stack at maxCnt becomes empty after a pop but maxCnt is not decremented. The next pop would then try to access an empty stack. Always check if the current frequency stack is empty after popping and reduce maxCnt accordingly.

Using a Single Stack and Scanning

While conceptually simple, maintaining a single stack and scanning backwards to find the most frequent recent element leads to O(n) pop operations. This approach times out on large inputs. The key insight is that elements can exist at multiple frequency levels simultaneously (when pushed multiple times), which the stack-of-stacks approach leverages for O(1) operations.

Heap Stale Entries

In the heap-based solution, old entries remain in the heap even after frequencies change through pops. While this doesn't affect correctness (since we decrement the frequency counter separately), it can cause memory bloat. Some implementations add lazy deletion, but the simpler approach is to accept that the heap may contain stale entries whose values no longer reflect current frequencies, relying on the frequency map as the source of truth.

class FreqStack:

    def __init__(self):
        self.cnt = {}
        self.stacks = [[]]

    def push(self, val: int) -> None:
        valCnt = 1 + self.cnt.get(val, 0)
        self.cnt[val] = valCnt
        if valCnt == len(self.stacks):
            self.stacks.append([])
        self.stacks[valCnt].append(val)

    def pop(self) -> int:
        res = self.stacks[-1].pop()
        self.cnt[res] -= 1
        if not self.stacks[-1]:
            self.stacks.pop()
        return res

class FreqStack {
public:
    unordered_map<int, int> cnt;
    vector<stack<int>> stacks;

    FreqStack() {
        stacks.push_back(stack<int>());
    }

    void push(int val) {
        int valCnt = ++cnt[val];
        if (valCnt == stacks.size()) {
            stacks.push_back(stack<int>());
        }
        stacks[valCnt].push(val);
    }

    int pop() {
        stack<int>& topStack = stacks.back();
        int res = topStack.top();
        topStack.pop();
        if (topStack.empty()) {
            stacks.pop_back();
        }
        cnt[res]--;
        return res;
    }
};