Maximum Frequency Stack: Stack of Stacks by Frequency

LeetCode Maximum Frequency Stack is problem 895, rated hard. It asks you to design a stack where pop does not remove the most recently pushed element. Instead, it removes the most frequent element. If there is a tie in frequency, the element closest to the top of the stack wins. This is one of those design problems where the trick is choosing the right combination of data structures. Once you see the pairing, the code is short and every operation runs in O(1).

The problem

Implement the FreqStack class:

• push(val) pushes an integer val onto the stack.
• pop() removes and returns the most frequent element in the stack. If there is a tie, the element closest to the top of the stack is removed.

fs = FreqStack()
fs.push(5)  # stack: [5]
fs.push(7)  # stack: [5, 7]
fs.push(5)  # stack: [5, 7, 5]
fs.push(7)  # stack: [5, 7, 5, 7]
fs.push(4)  # stack: [5, 7, 5, 7, 4]
fs.push(5)  # stack: [5, 7, 5, 7, 4, 5]
fs.pop()    # returns 5 (freq 3, the most frequent)
fs.pop()    # returns 7 (freq 2, tied with 5, but 7 was pushed more recently at freq 2)
fs.pop()    # returns 5 (freq 2)
fs.pop()    # returns 4 (freq 1, tied with 5 and 7, but 4 was pushed most recently at freq 1)

The approach

You need two hash maps working together:

1. freq: maps each value to its current frequency count. When you push 5 a third time, freq[5] becomes 3.
2. group: maps each frequency to a stack of values that have been pushed at that frequency. When you push 5 and its frequency becomes 3, you append 5 to group[3].

You also track maxfreq, the current maximum frequency across all values.

The key insight is that a single push adds the value to exactly one group. If you push 5 and its frequency goes from 2 to 3, you add 5 to group[3]. You do not remove it from group[2]. That copy of 5 in group[2] is still valid because it represents the "second occurrence" of 5.

On pop, you take the top element from group[maxfreq]. That gives you the most frequent element, and if there are ties, the one pushed most recently (because stacks are LIFO). Then you decrement that element's frequency. If group[maxfreq] is now empty, you decrement maxfreq.

This works because maxfreq can only decrease by 1 during a pop. You never skip a frequency level. Every value that reaches frequency f was first at frequency f-1, and those earlier copies are still sitting in group[f-1]. So when maxfreq drops from 3 to 2, group[2] is guaranteed to be non-empty.

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.group = {}
        self.maxfreq = 0

    def push(self, val):
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        if f > self.maxfreq:
            self.maxfreq = f
        if f not in self.group:
            self.group[f] = []
        self.group[f].append(val)

    def pop(self):
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return val

Step-by-step walkthrough

Let's trace through push(5), push(7), push(5), then push(7), push(4), push(5), followed by three pops. Watch how the freq map and group map evolve at each step.

Notice the pattern: each pop pulls from the highest frequency group, and when that group empties, maxfreq decreases by exactly 1. The lower frequency groups are always populated because every element passed through those levels on the way up.

Complexity analysis

Time: Both push and pop perform a constant number of hash map lookups, list appends, and list pops. All of these are O(1) amortized in Python.

Space: Each push adds one entry to a group stack and updates the freq map. Across n total pushes, the combined size of all group stacks is exactly n (each push adds exactly one element to one group). The freq map holds at most n distinct entries. Total space is O(n).

The building blocks

Frequency counting with a hash map

The freq map is the same frequency counting pattern you see in problems like Top K Frequent Elements and Group Anagrams. You maintain a running count for each element. The difference here is that the frequency changes over time as elements get pushed and popped, so the map is dynamic rather than built once from a static input.

Stack-indexed grouping

The group map is the more unusual piece. It maps each frequency level to a stack of elements at that level. This is sometimes called a "stack of stacks" pattern. The crucial property is that you only ever push to or pop from the stack at group[maxfreq], and maxfreq only changes by 1 at a time. This guarantee means you never need to search for the right group. You always know exactly which one to access.

Edge cases

• All elements the same. push(1), push(1), push(1). The freq map has one entry with value 3. The group map has three groups, each containing [1]. Pop returns 1 three times, decrementing maxfreq from 3 to 0.
• All elements unique. push(1), push(2), push(3). Every element has frequency 1. Pop returns elements in reverse push order (3, 2, 1), behaving like a normal stack.
• Tie-breaking. When multiple elements share the same maximum frequency, pop returns the one that was pushed most recently at that frequency level. The stack ordering within each group handles this automatically.
• Alternating push and pop. push(5), pop(), push(5), pop(). After each pop, the freq map resets 5's count. The next push starts fresh at frequency 1. The solution handles this because pop decrements the frequency, and the next push increments it again.

From understanding to recall

The code for FreqStack is short. Two maps, one integer, and about 15 lines of logic. But recreating it under pressure is harder than it looks. You need to remember that push appends to group[freq] without removing from lower groups. You need to remember that pop decrements both the frequency and (maybe) maxfreq. You need to remember that maxfreq only ever decreases by 1.

These details are easy to forget between practice sessions. Spaced repetition drilling locks them in. You write the FreqStack class from scratch at increasing intervals until the two-map structure and the maxfreq invariant become automatic. That is the difference between understanding the solution and being able to produce it in an interview.

Related posts

• LRU Cache - Another design problem pairing hash maps with a secondary structure for O(1) operations
• Min Stack - A simpler stack design problem where auxiliary tracking gives O(1) getMin
• Top K Frequent Elements - Uses frequency counting as a core building block, the same pattern that drives the freq map here
• LFU Cache - The closest relative to FreqStack, tracking frequency groups with similar data structure choices