Maximum Frequency Stack

Difficulty: Hard Source: NeetCode

Problem

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

FreqStack() Constructs an empty frequency stack.

void push(int val) Pushes an integer val onto the top of the stack.

int pop() Removes and returns the most frequent element in the stack. If there is a tie for the most frequent element, the element closest to the top of the stack (most recently pushed) is removed and returned.

Example 1: Input: [“FreqStack”,“push”,“push”,“push”,“push”,“push”,“push”,“pop”,“pop”,“pop”,“pop”], [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output: [null,null,null,null,null,null,null,5,7,5,4]

Explanation:

After pushes: [5,7,5,7,4,5]

pop() → 5 (frequency 3, the highest)

pop() → 7 (now 5 has freq 2, 7 has freq 2; 7 was pushed more recently at freq 2)

pop() → 5 (5 has freq 2 again since no pushes, 7 has freq 1; 5 was pushed more recently at freq 2)

pop() → 4

Constraints:

0 <= val <= 10^9

At most 2 * 10^4 calls will be made to push and pop.

It is guaranteed that there will be at least one element in the stack before calling pop.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash map — Two maps are needed: one for element frequencies, one mapping frequency levels to their stacks.
Stack — Each frequency level maintains its own stack to handle tie-breaking by recency.

The challenge is handling two competing requirements: pop the most frequent element, and if there is a tie, pop the most recently pushed one. The key insight is to maintain a separate stack for each frequency level. When you push an element, increment its frequency and append it to the stack for that frequency. When you pop, look at the highest frequency level and pop from its stack. If that stack becomes empty, decrement max_freq.

Think of it like shelves in a library: frequency level 1 is the bottom shelf, level 2 is above it, etc. Elements move up shelves as they get pushed more. To pop, take from the top of the highest non-empty shelf.

Algorithm

push(val):

Increment freq[val] (default 0).
Update max_freq = max(max_freq, freq[val]).
Append val to group[freq[val]] (the stack for that frequency).

pop():

Pop val from group[max_freq].
Decrement freq[val].
If group[max_freq] is now empty, decrement max_freq.
Return val.

Solution

from collections import defaultdict

class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)       # val -> current frequency
        self.group = defaultdict(list)     # frequency -> stack of vals at that freq
        self.max_freq = 0

    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        self.max_freq = max(self.max_freq, f)
        self.group[f].append(val)

    def pop(self) -> int:
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        # If no more elements at max_freq, the new max is one lower
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return val


# Test cases
fs = FreqStack()
fs.push(5)
fs.push(7)
fs.push(5)
fs.push(7)
fs.push(4)
fs.push(5)
print(fs.pop())  # Expected: 5  (freq 3)
print(fs.pop())  # Expected: 7  (freq 2, but 7 was pushed more recently than 5 at freq 2)
print(fs.pop())  # Expected: 5  (freq 2)
print(fs.pop())  # Expected: 4  (freq 1, but 4 was pushed more recently at freq 1)

# Additional test: all same elements
fs2 = FreqStack()
fs2.push(1)
fs2.push(1)
fs2.push(1)
print(fs2.pop())  # Expected: 1
print(fs2.pop())  # Expected: 1
print(fs2.pop())  # Expected: 1

Complexity

Time: O(1) for both push and pop — all operations are hash map lookups and stack push/pop.
Space: O(n) — the frequency map and group map together hold n total entries across all frequency levels.

Common Pitfalls

Trying to maintain a single sorted structure. A heap or sorted container would give O(log n) — the group map approach achieves O(1) by exploiting the structure of frequency increments (they only go up by 1 at a time).

Decrementing max_freq too eagerly. Only decrement max_freq when group[max_freq] is actually empty. If there are still other elements at that frequency level, max_freq should stay.

Confusing the semantics of group. group[f] is a stack (last-in-first-out) of elements whose frequency was f at the moment they were pushed. An element appears at multiple frequency levels — at level 1 when first pushed, level 2 on the second push, etc. Popping removes it from its highest level.

Note Book