#895 Maximum Frequency Stack

frequently reported atAmazon Microsoft Google

the problem

In plain words

Design FreqStack, a stack with a twist. push(val) puts val on top as usual. pop() removes and returns the value that appears most often in the stack right now; if several values tie, it removes the copy of the one closest to the top. pop is only called when the stack is not empty.

in push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop(), pop(), pop()

out 5, 7, 5, 4

First 5 is the most frequent (3 copies). Then 5 and 7 tie at 2, and the 7 is nearer the top. Then 5 (2 copies). Then 4, 5 and 7 tie at 1, and 4 is nearest the top.

0 ≤ val ≤ 10⁹
At most 2·10⁴ calls to push and pop
pop is only called on a non-empty stack

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack & queue design Frequency counting

Give each count its own stack. When a value reaches count f, push it onto stack f. The answer to pop is always the top of the highest stack — the most frequent value, and among ties the newest. Counts move by one per call, so the highest stack is found without searching.

solutions

From brute force to optimal

Keep the stack as a list plus a count map; pop finds the highest count, then the value nearest the top with that count.

push: append; count++.
pop: scan the counts for the maximum.
Walk the list from the top; remove the first value whose count equals the maximum; count--.

timepush O(1), pop O(n)

pop scans every count and walks the list; removing from the middle shifts the elements above it.

spaceO(n)

The list plus one count per distinct value.

javajava.util.* · java.util.function.*

1// On LeetCode, name this class FreqStack.2class FreqStackScan {3    private final List<Integer> stack = new ArrayList<>();      // bottom → top4    private final Map<Integer, Integer> freq = new HashMap<>(); // value → copies in the stack5 6    public void push(int val) {7        stack.add(val);8        freq.merge(val, 1, Integer::sum);9    }10 11    public int pop() {12        int max = 0;13        for (int f : freq.values()) max = Math.max(max, f); // the highest count: O(n)14        for (int i = stack.size() - 1; ; i--) {             // from the top down, so ties go to the newest15            int val = stack.get(i);16            if (freq.get(val) == max) {17                stack.remove(i);                            // shifts what was above it: O(n)18                freq.merge(val, -1, Integer::sum);19                return val;20            }21        }22    }23}

Every push adds an entry {count after this push, push number, value}. The heap's top is the most frequent and, among ties, the newest.

push: f = freq.merge(val, 1); offer {f, pushNumber++, val}.
pop: poll the top entry; freq[val]--; return val.

timeO(log n) per call

One heap offer or poll over at most n entries.

spaceO(n)

One heap entry per element still in the stack.

javajava.util.* · java.util.function.*

1// On LeetCode, name this class FreqStack.2class FreqStackHeap {3    private final Map<Integer, Integer> freq = new HashMap<>();4    // entry = {count after this push, push number, value}: biggest count first, then the newest push5    private final PriorityQueue<int[]> heap = new PriorityQueue<>(6            (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(b[1], a[1]));7    private int pushes = 0;8 9    public void push(int val) {10        int f = freq.merge(val, 1, Integer::sum);11        heap.offer(new int[] {f, pushes++, val}); // O(log n)12    }13 14    public int pop() {15        int val = heap.poll()[2]; // O(log n)16        freq.merge(val, -1, Integer::sum);17        return val;18    }19}

freq: value → count. group: count f → stack of the values that reached f. maxFreq: the highest count in use.

push: f = freq.merge(val, 1); maxFreq = max(maxFreq, f); push val onto group[f].
pop: val = group[maxFreq].pop(); freq[val]--.
If group[maxFreq] is now empty, maxFreq--. (Group maxFreq − 1 still holds val, so it is never empty.)

timeO(1) per call (average, for the HashMaps)

A fixed number of map operations and one stack push or pop — no scan, no heap.

spaceO(n)

A value with count f sits in f groups, but that is still one group entry per push in the stack: n in total.

javajava.util.* · java.util.function.*

1class FreqStack {2    private final Map<Integer, Integer> freq = new HashMap<>();          // value → copies in the stack3    private final Map<Integer, Deque<Integer>> group = new HashMap<>(); // count f → values that reached f, newest on top4    private int maxFreq = 0;5    // invariant: a value with count f sits once in each of group 1, 2, …, f6 7    public void push(int val) {8        int f = freq.merge(val, 1, Integer::sum);9        maxFreq = Math.max(maxFreq, f);10        group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(val);11    }12 13    public int pop() {14        Deque<Integer> top = group.get(maxFreq); // the most frequent values15        int val = top.pop(); // the newest of them wins the tie16        freq.merge(val, -1, Integer::sum);17        if (top.isEmpty()) maxFreq--; // group maxFreq − 1 still holds val, so it is never empty18        return val;19    }20}

sim

Dry run

loading simulation…

javajava.util.* · java.util.function.*

1class FreqStack {2    private final Map<Integer, Integer> freq = new HashMap<>();          // value → copies in the stack3    private final Map<Integer, Deque<Integer>> group = new HashMap<>(); // count f → values that reached f, newest on top4    private int maxFreq = 0;5    // invariant: a value with count f sits once in each of group 1, 2, …, f6 7    public void push(int val) {8        int f = freq.merge(val, 1, Integer::sum);9        maxFreq = Math.max(maxFreq, f);10        group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(val);11    }12 13    public int pop() {14        Deque<Integer> top = group.get(maxFreq); // the most frequent values15        int val = top.pop(); // the newest of them wins the tie16        freq.merge(val, -1, Integer::sum);17        if (top.isEmpty()) maxFreq--; // group maxFreq − 1 still holds val, so it is never empty18        return val;19    }20}

in the room

How to say it in the interview

talk track

Restate the tie rule with the example: 5 and 7 both have count 2, and the 7 is nearer the top.
Brute force: scan on pop, O(n). Better: a heap by (count, push order), O(log n).
Then the O(1) idea: one stack per count plus maxFreq. Explain why a value sits in groups 1 to f.
Justify maxFreq-- without a search: the value just popped is still in the group below.

traps

Moving a value out of group f when it reaches f + 1 — it must stay in every group up to its count; push it onto group f + 1 only.
Forgetting freq.merge(val, -1, Integer::sum) on pop.
Scanning for a new maximum after pop — maxFreq - 1 is always right.
Using the legacy Stack class; ArrayDeque is the modern stack.

what they ask next

Follow-ups

Pop the least frequent instead?

Then the extreme is no longer always next door: after a pop the lowest count may jump to any higher group. Keep the groups in a TreeMap from count to values (firstKey is the minimum, O(log n)), or use LFU-style count buckets linked in order.

How does this relate to LFU Cache (LC 460)?

LFU also groups keys by use count and evicts from the lowest group, with least-recently-used order inside a group. Same "bucket per count" idea, aimed at the minimum.

before you submit

Edge cases to test

All counts equal: FreqStack behaves exactly like a normal stack.
One value pushed many times: every pop returns it.
A count that drops and rises again: the value goes back on top of the group it re-enters.
Emptying the stack completely and then using it again.

practise next