Maximum Frequency Stack

HardHash Map + Stacks · Design🧩 Data Structure Design LeetCode #895 ↗Updated Oct 30, 2026

Problem

Design a stack-like class FreqStack. push(val) adds an integer; pop() removes and returns the value that currently occurs most often in the stack. If several values tie on frequency, pop the one whose occurrence was pushed most recently.

Inputpush 5,7,5,7,4,5 then pop()Output5

Inputpop() pop() pop()Output7, 5, 4

0 ≤ val ≤ 10⁹ · ≤ 2·10⁴ calls · pop only on a non-empty stack

Try it yourself

Java

class FreqStack {
    public void push(int val) {
        
    }

    public int pop() {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Think of the stack as layers by frequency: the k-th copy of a value goes onto stack k. Each layer is itself in push order, so the top of the highest layer is always the answer — and popping it never disturbs lower layers.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceOne Stack + Counts, Scan on Pop

Time O(1) push, O(n) popSpace O(n)

Keep a plain list in push order plus a frequency map. On pop, scan from the top down and keep the first value with a strictly larger count — scanning top-down makes ties resolve to the most recent one.

Java

class FreqStack {
    private final List<Integer> stack = new ArrayList<>();
    private final Map<Integer, Integer> freq = new HashMap<>();

    public void push(int val) {
        stack.add(val);
        freq.merge(val, 1, Integer::sum);
    }

    public int pop() {
        int best = -1;
        for (int i = stack.size() - 1; i >= 0; i--) {
            if (best == -1 || freq.get(stack.get(i)) > freq.get(stack.get(best))) best = i;
        }
        int val = stack.remove(best);   // O(n) shift
        freq.merge(val, -1, Integer::sum);
        return val;
    }
}

Straightforward, but every pop scans and shifts the whole stack.

BetterMax-Heap of (freq, time, val)

Time O(log n) push/popSpace O(n)

On each push, record the value's new frequency and a global timestamp, and add {freq, time, val} to a heap ordered by frequency, then time. The older entry of a popped value (one frequency lower) is still in the heap, so it correctly competes later.

Java

class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    private final PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
    private int time = 0;

    public void push(int val) {
        int f = freq.merge(val, 1, Integer::sum);
        heap.offer(new int[]{f, time++, val});
    }

    public int pop() {
        int val = heap.poll()[2];
        freq.merge(val, -1, Integer::sum);
        return val;
    }
}

Logarithmic and easy to justify, but the heap is overkill for this structure.

OptimalFrequency Map + Stack per Frequency

Time O(1) push/popSpace O(n)

freq counts each value and group[f] is a stack of values that reached frequency f. Push the value onto group[newFreq]; pop from group[maxFreq], and if it empties, maxFreq--. Frequencies grow by 1, so layer maxFreq-1 is never empty.

Java

class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    private final Map<Integer, Deque<Integer>> group = new HashMap<>();
    private int maxFreq = 0;

    public void push(int val) {
        int f = freq.merge(val, 1, Integer::sum);
        maxFreq = Math.max(maxFreq, f);
        group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(val);
    }

    public int pop() {
        Deque<Integer> top = group.get(maxFreq);
        int val = top.pop();
        freq.merge(val, -1, Integer::sum);
        if (top.isEmpty()) maxFreq--;
        return val;
    }
}

True O(1) for both operations with a simple invariant.

Pro tip

A value with count 3 lives in layers 1, 2 and 3 at once — popping only removes its top copy, which is why no rebalancing is ever needed.

At a glance

Level	Approach	Time	Space
Brute Force	One Stack + Counts, Scan on Pop	`O(1) push, O(n) pop`	`O(n)`
Better	Max-Heap of (freq, time, val)	`O(log n) push/pop`	`O(n)`
Optimal	Frequency Map + Stack per Frequency	`O(1) push/pop`	`O(n)`

Common pitfalls

Moving a value between layers on push — keep old copies; just add to the new layer.
Scanning bottom-up in the brute force — ties then pop the oldest, not the newest.
Forgetting maxFreq-- when the top layer empties.

Interview tips

Restate the tie-break precisely: same frequency → most recently pushed.
Show the heap version first; then ask what order the heap really needs.
Draw the layers for 5,7,5,7,4,5 to prove the invariant.

Pattern

Bucket of stacks by count → O(1) “most frequent, then most recent” queries.

My notes saved in this browser