Maximum Frequency Stack

Design FreqStack, a stack-like structure where push(val) adds a value and pop() removes and returns the most frequent value in it. If several values tie for most frequent, pop the one closest to the top (pushed most recently). This is LeetCode 895.

Example 1
Input: push 5, 7, 5, 7, 4, 5, then pop() four times
Output: 5, 7, 5, 4
Explanation: 5 appears 3 times, so it goes first. Then 5 and 7 both appear twice, and 7 was pushed more recently. Then 5 (twice) beats 4 and 7 (once). Then 4, 5 and 7 all appear once, and 4 is the most recent.

How to Think About It

Step 1: Two things decide the order

First the frequency, then recency. A priority queue ordered by (frequency, push time) works in O(log n) per call. There is an O(1) way.

Step 2: One stack per frequency level

When a value is pushed for the f-th time, push it onto the stack for level f. So a value that has been pushed 3 times appears on the stacks for levels 1, 2 and 3, once each.

  • The highest level holds exactly the values with the maximum frequency.
  • Inside a level, the top is the one that reached that frequency most recently, which is the one pushed most recently.

Step 3: pop

Pop from the highest level, lower that value's count by one, and drop the level if it became empty. The value's copy on the level below stays, which is right: its frequency is now one less.

Walkthrough

After pushing 5, 7, 5, 7, 4, 5 the levels are (bottom to top):

StepLevel 1Level 2Level 3Returns
after the pushes5, 7, 45, 75
pop()5, 7, 45, 7(removed)5
pop()5, 7, 457
pop()5, 7, 4(removed)5
pop()5, 74

Java Solution

The class files each pushed value under the frequency it reaches, so the most frequent and most recent value is always on top of the last group.

  • freq.merge(val, 1, Integer::sum): it increments the count and returns the new value f in one call.
  • Groups by level: groups.get(f - 1) holds the values that reached frequency f. A value pushed three times sits in groups 1, 2 and 3, which is how it can be popped three times.
  • Ties: inside a group the newest value is on top, so after 5 is popped the first time, 7 beats the older 5 at frequency 2.
  • Removing an empty group: when the top group empties, it is removed, so groups.size() stays equal to the current maximum frequency.

A common mistake is forgetting freq.merge(val, -1, Integer::sum) in pop. The count then runs ahead of the groups: push(5), push(5), pop(), push(5) computes frequency 3 and groups.get(2) throws an IndexOutOfBoundsException.

Java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    // groups.get(f - 1): values in the order they reached frequency f
    private final List<Deque<Integer>> groups = new ArrayList<>();

    public void push(int val) {
        int f = freq.merge(val, 1, Integer::sum);
        if (f > groups.size()) {
            groups.add(new ArrayDeque<>());
        }
        groups.get(f - 1).push(val);
    }

    public int pop() {
        Deque<Integer> top = groups.get(groups.size() - 1); // highest frequency
        int val = top.pop(); // most recent among them
        if (top.isEmpty()) {
            groups.remove(groups.size() - 1);
        }
        freq.merge(val, -1, Integer::sum);
        return val;
    }
}

The original implementation, FreqStack.java, is on GitHub.

Complexity

  • Time: O(1) per push and pop. Each call does one HashMap merge (O(1) on average), one deque push or pop, and at most one add or remove at the end of the ArrayList.
  • Space: O(n) over all levels: each push adds exactly one entry to one group, so the groups together hold at most n values, and the map has one count per distinct value.

Grouping items into buckets by frequency is also the idea in Top K Frequent Elements.