Maximum Frequency Stack
Last Updated: April 4, 2026
Understanding the Problem
We need to build a special stack where pop doesn't just remove the top element. Instead, it removes the element that appears most frequently. If multiple elements share the highest frequency, we break the tie by choosing the one that was pushed most recently (closest to the top).
This is tricky because a normal stack only cares about insertion order, and a normal priority queue only cares about some priority. Here we need both: frequency as the primary sort key, and recency as the tiebreaker. The question is how to combine these two dimensions efficiently.
The key observation is that frequency naturally forms "layers." When an element is pushed for the first time, it appears at frequency 1. When pushed again, it also appears at frequency 2. Think of each push as adding the element to a new frequency level. When we pop, we always pop from the highest frequency level, and within that level we want the most recently added element. That sounds a lot like maintaining a stack per frequency level.
Key Constraints:
0 <= val <= 10^9-> Values can be very large, so we can't use a fixed-size array indexed by value. A hash map is needed for tracking frequencies.At most 2 * 10^4 calls to push and pop-> With 20,000 operations, even an O(n) approach per call would finish in time. But the problem is a design question, so interviewers expect O(1) per operation.At least one element before pop-> We don't need to handle empty-stack edge cases for pop.
Approach 1: Brute Force with Sorting
Intuition
The most straightforward idea: every time we pop, scan through all elements in the stack, find the one with the highest frequency, and among ties pick the most recently pushed one. We can simulate this by keeping the full push history and computing frequencies on the fly.
Think of it as replaying the stack's history each time we need to make a decision. It's simple to reason about, and it gets the job done for small inputs.
Algorithm
- Maintain a list
stackthat stores elements in push order. - For
push(val): appendvalto the end of the list. - For
pop(): count the frequency of each element in the list. Find the maximum frequency. Among all elements with that frequency, find the one that appears latest in the list (highest index). Remove it from the list and return it.
Example Walkthrough
Input:
For pop(): scan stack [5,7,5,7,4,5]. Frequencies: 5->3, 7->2, 4->1. Max frequency is 3 (only element 5). Rightmost 5 is at index 5. Remove it.
Code
- Time Complexity: O(n) per pop, O(1) per push. Each pop scans the entire stack to compute frequencies, then scans again to find the rightmost max-frequency element. The list removal is also O(n) due to shifting.
- Space Complexity: O(n). We store all pushed elements in a list, and each pop creates a temporary frequency map of size at most n.
This approach recomputes frequencies from scratch on every pop. What if we maintained frequency counts incrementally and used a data structure that keeps elements sorted by frequency?
Approach 2: Heap-Based Priority Queue
Intuition
The brute force recomputes everything on each pop. A natural improvement is to maintain a max-heap (priority queue) that keeps elements sorted by frequency, with recency as a tiebreaker.
Every time we push a value, we increment its frequency and insert a new entry into the heap with (frequency, timestamp, value). The heap naturally gives us the element with the highest frequency. If two elements have the same frequency, the one with the higher timestamp (pushed more recently) comes out first.
The heap encodes both priorities we need: frequency and recency. By storing (frequency, timestamp, value) and using a max-heap, the element with the highest frequency always floats to the top. When two elements share the same frequency, the one with the larger timestamp (pushed more recently) wins the tiebreaker.
The clever part is that we don't need to update existing heap entries when an element's frequency changes. Each push adds a fresh entry with the current frequency. Old entries with lower frequencies remain in the heap but will naturally be extracted later, when the frequency counts have decreased enough for them to become relevant again.
Algorithm
- Maintain a hash map
freqthat tracks the current frequency of each value. - Maintain a max-heap where each entry is
(frequency, timestamp, value). - Keep a global
timestampcounter that increments on each push. - For
push(val): incrementfreq[val], incrementtimestamp, and add(freq[val], timestamp, val)to the heap. - For
pop(): extract the max element from the heap. This gives the element with the highest frequency (and highest timestamp among ties). Decrementfreq[val]for the popped value. Return the value.
Example Walkthrough
Code
- Time Complexity: O(log n) per push and pop. Both involve a heap insertion or extraction, each O(log n). The frequency map operations are O(1).
- Space Complexity: O(n). The heap stores one entry per push operation. Even after pops, stale lower-frequency entries remain.
The heap approach works but adds an unnecessary log n factor. Since we only ever need the maximum frequency, what if we grouped elements by frequency level and tracked the max directly?
Approach 3: Frequency-Grouped Stacks (Optimal)
Intuition
Here's the key insight that makes O(1) possible. When you push an element and its frequency increases from, say, 2 to 3, think of it as that element now "existing" at frequency level 3. If you maintain a separate stack for each frequency level, then popping becomes trivial: just pop from the stack at the highest frequency level.
Each frequency level's stack preserves the push order for elements at that level. The most recently pushed element at the max frequency level is exactly the element we want to pop. And we don't need to remove elements from lower frequency stacks, because those copies represent the element's presence at lower frequencies, which becomes relevant again after we've popped the higher-frequency occurrence.
The brilliance of this approach is that it turns the two-dimensional sorting problem (frequency + recency) into a simple stack-per-level structure where both dimensions are naturally handled.
When an element reaches frequency f, it gets pushed onto the frequency-f stack. The stack order within each level preserves insertion order, so the most recently pushed element at any frequency level is always on top. The maxFreq variable lets us instantly know which level to pop from.
The reason we can simply decrement maxFreq when the top stack becomes empty is subtle but important. Every element at frequency f also has an entry at frequency f-1 (from when it was pushed earlier). So the frequency-f stack can only become empty after we've popped from it, and at that point frequency f-1 still has elements. This means maxFreq can only decrease by exactly 1.
Algorithm
- Maintain a hash map
freqmapping each value to its current frequency. - Maintain a hash map
freqToStackmapping each frequency level to a stack (list) of values at that level. - Track
maxFreq, the current maximum frequency across all elements. - For
push(val): incrementfreq[val], appendvaltofreqToStack[freq[val]], updatemaxFreq. - For
pop(): pop the top value fromfreqToStack[maxFreq], decrementfreq[val], if the stack is now empty decrementmaxFreq. Return the popped value.
Example Walkthrough
Code
- Time Complexity: O(1) per push and pop. Push involves one hash map lookup, one stack push, and one comparison. Pop involves one stack pop, one hash map update, and one comparison. All constant time.
- Space Complexity: O(n). We store each pushed element once in a frequency stack, plus an entry in the frequency map.