LeetCode 895: Maximum Frequency Stack

Problem Restatement

Design a data structure called FreqStack.

It must support two operations:

Operation	Meaning
push(val)	Push integer val onto the stack
pop()	Remove and return the value with highest frequency

If multiple values have the same highest frequency, pop() must remove and return the one that was pushed most recently.

So this is like a stack, but priority is based on:

1. Higher frequency first.
2. More recent push first when frequencies tie.

LeetCode guarantees that pop() is only called when the stack has at least one element. The constraints allow at most 2 * 10^4 calls to push and pop.

Input and Output

Item	Meaning
Constructor	FreqStack() creates an empty data structure
Input to push	Integer val
Output of pop	Integer removed from the stack
Main rule	Pop the most frequent value
Tie rule	If tied, pop the most recently pushed value

Class shape:

class FreqStack:

    def __init__(self):
        ...

    def push(self, val: int) -> None:
        ...

    def pop(self) -> int:
        ...

Examples

Example:

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]

Operations:

freqStack = FreqStack()
freqStack.push(5)
freqStack.push(7)
freqStack.push(5)
freqStack.push(7)
freqStack.push(4)
freqStack.push(5)

Now the stack contains:

[5, 7, 5, 7, 4, 5]

Frequencies:

Value	Frequency
5	3
7	2
4	1

So the first pop() returns 5.

After removing one 5, frequencies become:

Value	Frequency
5	2
7	2
4	1

Now 5 and 7 are tied, but 7 was pushed more recently than the remaining 5, so the next pop() returns 7.

The next pops return 5, then 4.

First Thought: Scan the Whole Stack on Pop

A direct approach is to keep a normal stack list.

For push, append the value.

For pop, scan the entire stack to find:

1. The highest frequency.
2. Among values with that frequency, the most recent occurrence.

This works, but it makes pop() expensive.

If there are many operations, repeatedly scanning the whole stack can be too slow.

Key Insight

Group values by their current frequency.

Maintain:

Structure	Meaning
freq[val]	Current frequency of value val
group[f]	Stack of values that reached frequency f
max_freq	Current highest frequency in the data structure

When we push a value:

1. Increase its frequency.
2. Push it into the stack for that new frequency.
3. Update max_freq.

When we pop:

1. Look at group[max_freq].
2. Pop from that stack.
3. Decrease that value's frequency.
4. If group[max_freq] becomes empty, decrease max_freq.

This works because group[f] stores values in the order they reached frequency f. Therefore, the top of group[max_freq] is the most recently pushed value among all values with the highest frequency.

Algorithm

Initialize:

freq = {}
group = defaultdict(list)
max_freq = 0

For push(val):

1. Increment freq[val].
2. Let f = freq[val].
3. Append val to group[f].
4. Set max_freq = max(max_freq, f).

For pop():

1. Pop val from group[max_freq].
2. Decrement freq[val].
3. If group[max_freq] is empty, decrement max_freq.
4. Return val.

Walkthrough

Push sequence:

5, 7, 5, 7, 4, 5

After all pushes:

Frequency	Stack
1	[5, 7, 4]
2	[5, 7]
3	[5]

max_freq = 3.

First pop():

group[3].pop() -> 5

Now group[3] is empty, so max_freq becomes 2.

Second pop():

group[2].pop() -> 7

This returns 7, because among values with frequency 2, 7 reached that frequency most recently.

Third pop():

group[2].pop() -> 5

Now group[2] is empty, so max_freq becomes 1.

Fourth pop():

group[1].pop() -> 4

The return sequence is:

5, 7, 5, 4

Correctness

The dictionary freq always stores the current number of active occurrences for each value.

When push(val) is called, the value gains one occurrence, so increasing freq[val] is correct. If the new frequency is f, appending val to group[f] records that this push made val reach frequency f.

For any frequency f, group[f] is a stack ordered by the time values reached frequency f. Therefore, the last value in group[f] is the most recent value among all values that currently have reached that frequency and have not yet been removed from that frequency group.

max_freq stores the highest current frequency. Therefore, group[max_freq] contains the correct candidates for pop().

When pop() removes the top value from group[max_freq], it selects a value with highest frequency. Since it pops from a stack, it also selects the most recent value among ties.

After removal, that value's active frequency decreases by one. If no values remain in the old maximum frequency group, then the highest active frequency decreases by one.

Thus, each pop() returns exactly the value required by the problem.

Complexity

Operation	Time	Why
Constructor	O(1)	Initializes maps and counter
push	O(1)	Hash map update and list append
pop	O(1)	List pop and hash map update

Space complexity is O(n), where n is the number of active pushed elements plus stored frequency-group entries.

Implementation

from collections import Counter, defaultdict

class FreqStack:

    def __init__(self):
        self.freq = Counter()
        self.group = defaultdict(list)
        self.max_freq = 0

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

        self.group[f].append(val)

        if f > self.max_freq:
            self.max_freq = f

    def pop(self) -> int:
        val = self.group[self.max_freq].pop()

        self.freq[val] -= 1

        if not self.group[self.max_freq]:
            self.max_freq -= 1

        return val

Code Explanation

We use freq to count current frequencies:

self.freq = Counter()

We use group to store one stack per frequency:

self.group = defaultdict(list)

We track the current highest frequency:

self.max_freq = 0

On push, we update the value's frequency:

self.freq[val] += 1
f = self.freq[val]

Then we append the value to the stack for that frequency:

self.group[f].append(val)

On pop, we remove the most recent value from the highest-frequency stack:

val = self.group[self.max_freq].pop()

Then we decrease its active frequency:

self.freq[val] -= 1

If the highest-frequency stack is empty, no value currently has that frequency anymore:

if not self.group[self.max_freq]:
    self.max_freq -= 1

Finally, return the removed value.

Testing

def run_tests():
    fs = FreqStack()

    fs.push(5)
    fs.push(7)
    fs.push(5)
    fs.push(7)
    fs.push(4)
    fs.push(5)

    assert fs.pop() == 5
    assert fs.pop() == 7
    assert fs.pop() == 5
    assert fs.pop() == 4

    fs = FreqStack()
    fs.push(1)
    fs.push(2)
    fs.push(3)

    assert fs.pop() == 3
    assert fs.pop() == 2
    assert fs.pop() == 1

    fs = FreqStack()
    fs.push(1)
    fs.push(1)
    fs.push(2)
    fs.push(2)

    assert fs.pop() == 2
    assert fs.pop() == 1

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Official-style sequence	Checks frequency and recency tie-breaking
All frequencies equal	Behaves like normal stack
Equal high frequencies	Most recent among tied values is popped first