LeetCode 895: Maximum Frequency Stack

Problem Restatement

Design a data structure called FreqStack.

It must support two operations:

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

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:

So the first pop() returns 5.

After removing one 5, frequencies become:

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:

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:

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

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: