Start practising

Maximum Frequency Stack

Hard Design Data Structures Stack Original on LeetCode

Maximum Frequency Stack is a hard design data structures problem solved with the stack pattern. The best approach, optimal (stack per frequency level), runs in O(1) per operation time and O(n) space. Below are 2 approaches in Java, from heap with (frequency, push time) up.

Problem

Design a stack where pop removes and returns the most frequent element. If several elements are equally frequent, it removes the one closest to the top (pushed most recently).

Examples

Example 1

Input
push 5, 7, 5, 7, 4, 5; pop(); pop(); pop(); pop()
Output
5, 7, 5, 4
Why
5 (freq 3) → then 5 and 7 tie at 2, and 7 is closer to the top → then 5 → then 4, 7 tie at 1 and 4 is closer to the top.

Constraints

  • Up to 2 · 10^4 calls; pop is only called on a non-empty stack.
  • pop removes the most frequent element; ties go to the one pushed most recently.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Heap with (frequency, push time)O(log n) per operationO(n)
Optimal (stack per frequency level)O(1) per operationO(n)

1Heap with (frequency, push time)

TimeO(log n) per operation
SpaceO(n)

Push entries {value, frequency after push, timestamp} into a max-heap ordered by frequency, then by timestamp. Popping takes the heap top and lowers that value's frequency.

  1. push: freq[v]++; heap.add({v, freq[v], time++}).
  2. pop: e = heap.poll(); freq[e.v]--; return e.v.
Java
class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    private final PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] != b[1] ? b[1] - a[1] : b[2] - a[2]);
    private int time = 0;

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

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

2Optimal (stack per frequency level)

TimeO(1) per operation
SpaceO(n)

group[f] is a stack of values that reached frequency f, in push order. Pushing v with new frequency f adds it to group[f]. Earlier copies stay in lower groups, which is correct: after popping, v's frequency drops by one and its lower copy is still in the right place.

  1. push: f = ++freq[v]; maxFreq = max(maxFreq, f); group[f].push(v).
  2. pop: v = group[maxFreq].pop(); freq[v]--; if the group is empty, maxFreq--.
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() {
        int v = group.get(maxFreq).pop();
        freq.merge(v, -1, Integer::sum);
        if (group.get(maxFreq).isEmpty()) maxFreq--;
        return v;
    }
}

Edge cases to test

  • Ties in frequency
  • Pushing a value again after it was popped

Hints

Hint 1

Keep a separate stack for each frequency level. A value pushed for the 3rd time goes on stack 3. Pop from the highest non-empty level.

FAQ

What is the best time complexity for Maximum Frequency Stack?

Optimal (stack per frequency level) runs in O(1) per operation time and O(n) extra space.

Which pattern does Maximum Frequency Stack use?

It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Min Stack, Design a Stack With Increment Operation.

Is there a brute force solution for Maximum Frequency Stack?

Yes. Heap with (frequency, push time) takes O(log n) per operation time and O(n) space. Push entries {value, frequency after push, timestamp} into a max-heap ordered by frequency, then by timestamp.

Which edge cases should I test for Maximum Frequency Stack?

Ties in frequency; Pushing a value again after it was popped.