Maximum Frequency Stack — HashMap + Stack Groups (LeetCode 895)

Maximum Frequency Stack (LeetCode 895) asks you to design a stack-like structure where pop removes the most frequent element. If there is a tie, pop the one closest to the top (most recently pushed among the most frequent).

The Problem

push(5), push(7), push(5), push(7), push(4), push(5)

pop() → 5  (freq 3, most frequent)
pop() → 7  (freq 2, tied with 5; 7 was pushed more recently at freq 2)
pop() → 5  (freq 2, most frequent now)
pop() → 4  (freq 1, all tied; 4 was most recently pushed)

The Key Insight: Stack Groups by Frequency

Instead of one big stack, maintain one stack per frequency level:

• freq_map: element → current frequency
• group: frequency → stack of elements at that frequency
• max_freq: the current maximum frequency

When we push element x:

1. Increment its frequency in freq_map
2. Push it onto group[new_freq]
3. Update max_freq if needed

When we pop:

1. Pop from group[max_freq]
2. Decrement its frequency in freq_map
3. If group[max_freq] is now empty, decrement max_freq

This gives us O(1) for both push and pop.

Implementation

from collections import defaultdict

class FreqStack:
    """
    Maximum Frequency Stack — O(1) push and pop.
    Uses frequency → stack mapping.
    """
    def __init__(self):
        self.freq_map = defaultdict(int)  # element → frequency
        self.group = defaultdict(list)     # frequency → stack
        self.max_freq = 0

    def push(self, val: int) -> None:
        # Increment frequency
        self.freq_map[val] += 1
        freq = self.freq_map[val]

        # Push onto the stack for this frequency
        self.group[freq].append(val)

        # Update max frequency
        self.max_freq = max(self.max_freq, freq)

    def pop(self) -> int:
        # Pop from the most frequent group
        val = self.group[self.max_freq].pop()

        # Decrement frequency
        self.freq_map[val] -= 1

        # If this frequency group is empty, lower max_freq
        if not self.group[self.max_freq]:
            self.max_freq -= 1

        return val

Step-by-Step Trace

Operation         freq_map              group                       max_freq
─────────────────────────────────────────────────────────────────────────────
push(5)          {5:1}                 {1:[5]}                      1
push(7)          {5:1, 7:1}            {1:[5,7]}                    1
push(5)          {5:2, 7:1}            {1:[5,7], 2:[5]}             2
push(7)          {5:2, 7:2}            {1:[5,7], 2:[5,7]}           2
push(4)          {5:2, 7:2, 4:1}       {1:[5,7,4], 2:[5,7]}         2
push(5)          {5:3, 7:2, 4:1}       {1:[5,7,4], 2:[5,7], 3:[5]}  3

pop() → 5        {5:2, 7:2, 4:1}       {1:[5,7,4], 2:[5,7]}         2
  (popped from group[3], group[3] empty → max_freq = 2)

pop() → 7        {5:2, 7:1, 4:1}       {1:[5,7,4], 2:[5]}           2
  (popped from group[2], 7 was on top)

pop() → 5        {5:1, 7:1, 4:1}       {1:[5,7,4]}                  1
  (popped from group[2], group[2] empty → max_freq = 1)

pop() → 4        {5:1, 7:1, 4:0}       {1:[5,7]}                    1
  (popped from group[1], 4 was on top)

Why Not a Max-Heap?

A heap-based approach would store (frequency, push_order, value) tuples:

import heapq

class FreqStackHeap:
    """Heap approach — O(log n) push and pop."""
    def __init__(self):
        self.heap = []  # max-heap: (-freq, -order, val)
        self.freq_map = defaultdict(int)
        self.order = 0

    def push(self, val):
        self.freq_map[val] += 1
        heapq.heappush(self.heap,
            (-self.freq_map[val], -self.order, val))
        self.order += 1

    def pop(self):
        _, _, val = heapq.heappop(self.heap)
        self.freq_map[val] -= 1
        return val

This works but is O(log n) per operation. The stack-group approach is O(1).

Approach	Push	Pop	Space
Stack groups	O(1)	O(1)	O(n)
Max-heap	O(log n)	O(log n)	O(n)

Why the Stack-Group Trick Works

The critical insight is that an element with frequency f also existed at frequencies 1, 2, ..., f-1. So it appears in all groups from 1 to f. When we pop it from group f, it still exists in groups 1 through f-1. We do not need to remove it from lower groups — it will naturally be popped from there when max_freq drops.

This is why we only decrement freq_map[val] on pop, not remove from all groups.

Complexity Analysis

Operation	Time	Space
push	O(1)	O(n) total across all operations
pop	O(1)	—

The total space is O(n) where n is the total number of push operations, because each push adds exactly one entry to group.

Edge Cases

fs = FreqStack()

# Single element pushed multiple times
fs.push(1); fs.push(1); fs.push(1)
assert fs.pop() == 1  # freq 3 → 2
assert fs.pop() == 1  # freq 2 → 1
assert fs.pop() == 1  # freq 1 → 0

# All elements have the same frequency → LIFO order
fs2 = FreqStack()
fs2.push(1); fs2.push(2); fs2.push(3)
assert fs2.pop() == 3  # all freq 1, most recent
assert fs2.pop() == 2
assert fs2.pop() == 1

When to Use This Pattern

Use frequency-based stack grouping when:

• You need to track frequency alongside recency (stack order)
• The problem requires O(1) operations on a frequency-priority structure
• You see “most frequent” + “most recent tiebreaker” in the problem

Common Mistakes

1. Trying to remove from all groups on pop — only pop from max_freq group
2. Forgetting to decrement max_freq when the top group becomes empty
3. Using a heap instead — works but loses the O(1) guarantee

Related Problems

Problem	Key Difference
LFU Cache (LC 460)	Similar frequency tracking but with eviction
Min Stack (LC 155)	Track min instead of frequency
Stack with Increment (LC 1381)	Stack with lazy increment
Top K Frequent Elements (LC 347)	Frequency counting, different output

Key Takeaways

• The Maximum Frequency Stack uses one stack per frequency level — a powerful design trick
• Both push and pop are O(1) because we only touch the max_freq group
• Elements naturally exist in multiple frequency groups; no cleanup needed on pop
• This pattern (grouping by frequency + stack) appears in LFU cache designs too