HardHash TableStackDesignOrdered Set

Maximum Frequency Stack

1 approach, code in every language

Design a stack-like structure that always removes the most frequently pushed element.

Implement FreqStack with two operations: push(val) adds an integer to the structure, and pop() removes and returns the element that has been pushed most often. If several elements tie for the highest frequency, remove the one that was pushed most recently.

Example 1

Input: operations = ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"] arguments = [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]

Output: [null,null,null,null,null,null,null,5,7,5,4]

After the pushes, counts are 5:3, 7:2, 4:1. pop() returns 5 (most frequent), then 7 (now 5 and 7 both have count 2, 7 was pushed more recently), then 5, then 4.

Example 2

Input: operations = ["FreqStack","push","push","push","pop","pop"] arguments = [[],[1],[1],[2],[],[]]

Output: [null,null,null,null,1,1]

Counts after pushes are 1:2, 2:1. pop() returns 1 (highest frequency); the next pop() sees 1 and 2 both at count 1, and 1 was pushed most recently, so it returns 1 again.

Constraints

0 <= val <= 10^9
At most 2 * 10^4 calls will be made to push and pop
It is guaranteed that there is at least one element in the stack before each call to pop

Frequency Map + Per-Frequency Stacks

Track each value's count, keep a stack of values for every frequency level, and remember the current maximum frequency to serve pops in O(1).

Loading animation…

Intuition

Two things determine the pop order: how frequently a value has been pushed and, among equal frequencies, how recently. Track each value's current count in a freq map. Then, for each frequency level, keep a stack of the values that have reached that level, in push order. A running maxFreq points at the tallest level. Push increments the count and appends to that level's stack; pop takes the top of the maxFreq stack, which is exactly the most frequent and most recently pushed value. When a level's stack empties, decrement maxFreq.

Algorithm walkthrough

1Maintain freq (value -> count), group (frequency -> stack of values), and maxFreq.
2On push(val): increment freq[val] to f, update maxFreq if f is larger, and append val onto group[f].
3On pop(): take the top value from group[maxFreq]; this is the most frequent, most recently pushed element.
4Decrement that value's frequency in freq.
5If group[maxFreq] is now empty, decrease maxFreq by one.
6Return the popped value.

Implementation

from collections import defaultdict


class FreqStack:
    def __init__(self):
        self.freq: dict[int, int] = defaultdict(int)
        self.group: dict[int, list[int]] = defaultdict(list)
        self.max_freq = 0

    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        if f > self.max_freq:
            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 not self.group[self.max_freq]:
            self.max_freq -= 1
        return val

Time

O(1) per push and O(1) per pop

Space

O(n) for n elements currently stored

Each value can sit in multiple per-frequency stacks over its lifetime, but total storage stays proportional to the number of live pushes.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free