← DSA Atlas
Dedicated problem page · #895

Maximum Frequency Stack

HardData Structure DesignBucket elements by frequency, pop from the highest bucketFrequency map plus a stack per frequency level
Solve on LeetCode ↗
895
HardData Structure DesignFrequency map plus a stack per frequency levelBucket elements by frequency, pop from the highest bucket

Maximum Frequency Stack

Design a stack-like structure FreqStack. push(val) adds a value. pop() removes and returns the most frequent value; if several values tie for most frequent, return the one that was pushed most recently.

Open official problem prompt ↗
In plain English

Always return the element with the highest current occurrence count, breaking ties in favor of the most recently pushed value.

Picture it like this

Imagine stacking poker chips into columns by how many times a color has appeared: the first red chip goes in column 1, the second red in column 2, and so on. To pop, you grab the top chip of the tallest column.

Example
Input
FreqStack(); push(5); push(7); push(5); push(7); push(4); push(5); pop(); pop(); pop(); pop()
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]
Why
Counts are 5:3, 7:2, 4:1. pop returns 5 (freq 3); then 7 and 5 tie at freq 2 so the more recent 7 wins, then 5; then 4 at freq 1.
Constraints
0 <= val <= 10^9At most 2 * 10^4 calls to push and pop combinedIt is guaranteed pop is only called on a non-empty stack
Pattern lesson

See the pattern, then code

Bucket elements by frequency, pop from the highest bucket
Recognition clue

Pop order depends on how OFTEN a value appears, with recency as tie-break. Ranking by count plus LIFO tie-break points to grouping elements by their current frequency.

↗
Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. The nth occurrence of a value belongs to frequency-bucket n. Keeping each bucket as a stack means the top of the highest non-empty bucket is exactly the most-frequent, most-recent element.

New words, made simpleKnow these before the algorithm
Frequency bucket
A stack holding every value at the moment it reached a particular occurrence count.
maxfreq
The highest occurrence count any value currently has; the bucket to pop from.
LIFO tie-break
Among equally frequent values, the last pushed comes out first.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Scan for max frequency each pop

Recomputing counts every pop is far too slow.

Keep a full history list and, on pop, count frequencies to find the winner.

Time O(n) per popSpace O(n)
Best choiceFrequency buckets of stacks

Both operations are constant time and tie-breaking is automatic.

Push the nth copy of a value onto bucket n; pop from the top of the tallest bucket.

Time O(1) per operationSpace O(n)
The rule we keep true

Invariant

group[f] contains, in push order, exactly the values whose count reached at least f and is currently still at least f; the top of group[maxfreq] is the most-frequent, most-recent element.

Why this is correct

Reasoning

When a value hits count f it is appended to group[f], so the top of group[maxfreq] is the value that most recently reached the highest count. Popping it decrements only that value's count and removes its highest-bucket copy, exactly reversing the push and preserving the invariant.

The algorithm in three movesSay these aloud before coding
1Maintain freq[val] = current count of each value

freq={5:3,7:2,4:1} maxfreq=3

2Maintain group[f] = a stack of values that have reached frequency f

group[3]=[5], group[2]=[5,7], group[1]=[5,7,4]

3On push, bump freq[val] to f, append val to group[f], and raise maxfreq if needed

pop -> group[3].pop()=5, maxfreq drops to 2

4On pop, take the top of group[maxfreq], decrement its freq, and drop maxfreq when that bucket empties

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
50
71
52
73
44
55
1 · Readsix values
2 · AskWhich bucket does each copy land in?
3 · Update stategroup[1]=[5,7,4], group[2]=[5,7], group[3]=[5]
4 · Resultmaxfreq=3
Key takeaway

Values stacked into frequency buckets; pop takes the top of the tallest bucket (group[3]=[5]).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-7State

    freq tracks counts, group is the bucket-of-stacks, maxfreq is the tallest bucket index.

  2. 2
    Lines 9-14push

    Increment the count and append onto the bucket for that new count, updating maxfreq.

  3. 3
    Lines 16-21pop

    Pop the top of group[maxfreq], decrement the count, and lower maxfreq when the bucket drains.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All values distinct so every pop is pure LIFO at frequency 1
  • A single value pushed many times pops in strict reverse order
  • Repeated tie situations where recency must decide
  • Interleaved pushes that raise maxfreq back up after it dropped
!

Common beginner mistakes

  • Breaking ties by insertion order instead of recency (using a queue per bucket instead of a stack)
  • Forgetting to decrement freq[val] on pop, corrupting future bucket placement
  • Not lowering maxfreq when the top bucket empties, causing a pop from an empty list
  • Trying to also delete the popped value from lower buckets, which is unnecessary and wrong
Check your understanding

Why does appending each occurrence to group[freq] give correct recency tie-breaking for free?

More in Data Structure Design

#348Design Tic-Tac-ToeRunning line counters#355Design TwitterTimestamped feed merge#362Design Hit CounterSliding time window#432All O(1) Data StructureOrdered buckets by count#460LFU CacheFrequency buckets with per-bucket LRU#622Design Circular QueueRing buffer with head + size