Maximum Frequency Stack

Design a stack-like container FreqStack whose pop removes the value that appears most often instead of simply the newest one.

• FreqStack() creates an empty container.
• push(val) adds the integer val on top.
• pop() removes and returns one copy of the value that currently occurs the greatest number of times. If several values share that highest count, remove the copy that is closest to the top (the one pushed most recently among them).

pop is only called when the container is not empty.

Each test is a list of operation names and a matching list of argument lists; the expected output lists every return value, with null for the constructor and push.

Example 1

Example 2

Example 3

Constraints

• 0 <= val <= 109
• At most 2 × 10⁴ calls to push and pop in total.
• pop is never called on an empty container.

Pattern Path · Design · problem 168 of 169

Start simple

Store everything in a list and, on each pop, count frequencies and scan from the top for the first value with the maximum count: O(n) per pop.

The key idea

Two questions must be answered on every pop: which frequency is highest, and among values with that frequency, which is closest to the top. A heap ordered by (frequency, push time) works in O(log n), but there is a neater constant-time structure.

When val is pushed and its count becomes f, append it to groups[f], a plain stack for frequency level f. A value with count 3 therefore sits in levels 1, 2 and 3 at once. Track maxFreq, the highest non-empty level.

To pop, take the top of groups[maxFreq]. It has the highest frequency by definition, and it is the most recent of its level because each level is ordered by when values reached that count. Decrement its frequency. If that level is now empty, decrease maxFreq by one. This is safe: every value that was at level f is still present at level f-1, so the level below is never empty.

Notice that we never move an entry between levels. Removing the top copy simply exposes the value's lower-level entry, which is exactly the state it would be in had the last push never happened.

Complexity

• Time: O(1) per push and pop
• Space: O(n)

Python

from collections import Counter, defaultdict


class FreqStack:
    def __init__(self):
        self.freq = Counter()             # value -> copies currently in the stack
        self.groups = defaultdict(list)   # f -> values that reached frequency f, oldest first
        self.max_freq = 0

    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        self.groups[f].append(val)        # this copy is the f-th copy of val
        self.max_freq = max(self.max_freq, f)

    def pop(self) -> int:
        # The newest value in the highest group is both most frequent and closest to the top.
        val = self.groups[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.groups[self.max_freq]:
            self.max_freq -= 1
        return val

JavaScript

class FreqStack {
  constructor() {
    this.freq = new Map(); // value -> copies currently in the stack
    this.groups = [[]];    // groups[f] = values that reached frequency f, oldest first (index 0 unused)
  }

  push(val) {
    const f = (this.freq.get(val) || 0) + 1;
    this.freq.set(val, f);
    if (f === this.groups.length) this.groups.push([]);
    this.groups[f].push(val); // this copy is the f-th copy of val
  }

  pop() {
    // The newest value in the highest group is both most frequent and closest to the top.
    const top = this.groups[this.groups.length - 1];
    const val = top.pop();
    this.freq.set(val, this.freq.get(val) - 1);
    if (top.length === 0) this.groups.pop();
    return val;
  }
}

What the interviewer is checking

The interviewer is checking whether you can find a layered structure that makes both priorities (count, then recency) fall out naturally, instead of reaching straight for a heap and stopping there.

Mistakes to avoid

• Breaking ties by the time a value was first pushed instead of the time it reached the tied frequency.
• Scanning all values on every pop, which is linear per operation.
• Forgetting to lower maxFreq once its level becomes empty.
• Removing a value from all levels on pop; only the top-level copy should go.

Follow-ups to expect

• How would a heap-based version work? (Key: frequency, then push sequence number.)
• Add a peek() that does not remove. (Read the top of the max level.)
• Support removing the least frequent value instead. (Track a min level; harder after pops.)

In real software

Bucketing items by count with a stack per bucket is how LFU caches and "most active" feeds pick a victim or a highlight in constant time while still respecting recency.

Practice next