895. Maximum Frequency Stack

hard

Design a stack where pop returns the most frequent element, ties broken by recency. The 'aha' design problem — a stack of stacks indexed by frequency gives O(1) operations.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-25

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 stack's top is removed and returned.

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.

Examples

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 all pushes, 5 appears 3 times, 7 appears 2 times, 4 appears once. pop() -> 5 (most frequent). pop() -> 7 (now tied with 5 at 2, but 7 is more recent). pop() -> 5. pop() -> 4.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Use a map from value to current frequency.

Hint 2

Use a 'group' map: frequency -> stack of values pushed at that frequency level. Push x onto group[freq[x]+1] after incrementing.

Hint 3

Track maxFreq globally. Pop comes from group[maxFreq] — the top is automatically the most recent push at that frequency.

Hint 4

When you pop, if group[maxFreq] becomes empty, decrement maxFreq.

Solution approach

Reveal approach

Two maps + a max-frequency counter. freq: value -> count. groups: frequency -> stack of values. maxFreq: int. push(x): freq[x]++; push x onto groups[freq[x]]; maxFreq = max(maxFreq, freq[x]). The key insight: pushing x at its new frequency level preserves the original push order within each level — so the top of groups[maxFreq] is automatically the most-recently-pushed value among the most-frequent values (ties broken by recency for free). pop(): x = groups[maxFreq].pop(); freq[x]--; if groups[maxFreq] is empty, maxFreq--. Return x. Both operations are O(1). The same value appears in multiple group stacks (one entry per frequency level it's reached) — total space is O(total pushes).

Complexity

Time: O(1) per op
Space: O(n)

Related patterns

stack
hash-map
design

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

Amazon
Google
Bloomberg

Practice these live with InterviewChamp.AI

Drill Maximum Frequency Stack and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →