AlgoMaster Logo

Maximum Frequency Stack

hardFrequency8 min readUpdated June 23, 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.

Frequency forms layers. When an element is pushed for the first time, it sits at frequency 1. When pushed again, it also sits at frequency 2, and so on. Each push raises the element to one higher frequency level. When we pop, we want the highest occupied frequency level, and within that level the most recently added element. That maps to maintaining one 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 finishes in time. The target is still O(1) per operation, which the structure below achieves.
  • 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

Keep the full push history in a list. Every time we pop, scan the entire list, count the frequency of each element, find the highest frequency, and among ties pick the element that appears latest in the list. This recomputes everything from scratch on each pop, which is slow but easy to verify against the problem definition.

Algorithm

  1. Maintain a list stack that stores elements in push order.
  2. For push(val): append val to the end of the list.
  3. 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:

0
push(5)
1
push(7)
2
push(5)
3
push(7)
4
push(4)
5
push(5)
6
pop()
7
pop()
8
pop()
9
pop()
operations

After the six pushes the list is [5, 7, 5, 7, 4, 5]. We then run four pops:

  • pop 1: Frequencies are 5->3, 7->2, 4->1. Max is 3, held only by 5. Rightmost 5 is at index 5. Remove it. Return 5. List becomes [5, 7, 5, 7, 4].
  • pop 2: Frequencies are 5->2, 7->2, 4->1. Max is 2, held by 5 and 7. The rightmost element with frequency 2 is the 7 at index 3. Remove it. Return 7. List becomes [5, 7, 5, 4].
  • pop 3: Frequencies are 5->2, 7->1, 4->1. Max is 2, held only by 5. Rightmost 5 is at index 2. Remove it. Return 5. List becomes [5, 7, 4].
  • pop 4: Frequencies are 5->1, 7->1, 4->1. Max is 1, held by all three. The rightmost is the 4 at index 2. Remove it. Return 4. List becomes [5, 7].
0
5
1
7
2
5
3
4
result

Code

Recomputing frequencies from scratch on every pop is the bottleneck. The next approach maintains frequency counts incrementally and uses a heap to keep elements ordered by frequency.

Approach 2: Heap-Based Priority Queue

Intuition

Maintain a max-heap (priority queue) ordered by frequency, with recency as the tiebreaker. Each push increments the value's frequency and inserts a new entry (frequency, timestamp, value) into the heap. The heap's top is the entry with the highest frequency, and among equal frequencies the one with the larger timestamp (pushed more recently).

A push never updates an existing heap entry. It always inserts a fresh entry carrying the value's current frequency. When the value was at frequency 2 and is pushed to frequency 3, both the (2, ...) and (3, ...) entries sit in the heap. The frequency-3 entry is extracted first because it has the higher frequency; the older frequency-2 entry stays and is extracted on a later pop, by which point the higher-frequency copies have already been removed. This is why stale entries do not cause wrong answers: an entry with frequency f is only at the top when no entry of frequency greater than f remains, and the value's frequency-f copy is exactly the occurrence that should be popped at that point.

Algorithm

  1. Maintain a hash map freq that tracks the current frequency of each value.
  2. Maintain a max-heap where each entry is (frequency, timestamp, value).
  3. Keep a global timestamp counter that increments on each push.
  4. For push(val): increment freq[val], increment timestamp, and add (freq[val], timestamp, val) to the heap.
  5. For pop(): extract the max element from the heap. This gives the element with the highest frequency (and highest timestamp among ties). Decrement freq[val] for the popped value. Return the value.

Example Walkthrough

1Initial: empty heap
[]
1/8
1Frequency map empty
1/8

Code

The heap adds a log n factor that is not needed: we only ever query the maximum frequency, not a full ordering. The next approach groups elements by frequency level and tracks the maximum directly, bringing both operations to O(1).

Approach 3: Frequency-Grouped Stacks (Optimal)

Intuition

When an element's frequency increases from 2 to 3, it now occupies frequency level 3. Maintain a separate stack for each frequency level. Popping reduces to popping from the stack at the highest occupied level.

Each level's stack preserves push order for the elements at that level, so the top of the max-frequency stack is the most recently pushed element there, which is exactly what we want. Lower-frequency stacks keep their entries: a value pushed three times has one entry on the level-1, level-2, and level-3 stacks. After we pop its level-3 copy, its level-2 copy is still present and becomes poppable once level 3 is exhausted. This turns the two-dimensional ordering (frequency, then recency) into a one-dimensional choice of which level's stack to pop.

Algorithm

  1. Maintain a hash map freq mapping each value to its current frequency.
  2. Maintain a hash map freqToStack mapping each frequency level to a stack (list) of values at that level.
  3. Track maxFreq, the current maximum frequency across all elements.
  4. For push(val): increment freq[val], append val to freqToStack[freq[val]], update maxFreq.
  5. For pop(): pop the top value from freqToStack[maxFreq], decrement freq[val], if the stack is now empty decrement maxFreq. Return the popped value.

Example Walkthrough

freqToStack
1Initial: empty frequency stacks, maxFreq=0
freq
1Frequency map empty
1/9

Code