895. Maximum Frequency Stack

NeetCode: Maximum Frequency Stack · LeetCode: 895. Maximum Frequency Stack · Difficulty: Hard

Design a stack-like structure FreqStack with two operations: push(val) pushes an integer, and pop() removes and returns the most frequent element in the stack. If several elements share the highest frequency, the one closest to the top of the stack (pushed most recently) is removed.

Example

push 5, push 7, push 5, push 7, push 4, push 5
pop -> 5   (5 appears three times)
pop -> 7   (5 and 7 tie at two; 7 was pushed more recently)
pop -> 5   (5 and 7 tie at two again; 5 is now more recent)
pop -> 4   (everything has frequency one; 4 is on top)

Brute force: scan on every pop

Keep the pushed values in an ArrayList<Integer>. On pop, count how often each value occurs, find the maximum count, then walk from the end of the list to the first element whose count equals that maximum, and remove it. push is O(1) and pop costs a full scan.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class FreqStack {
    private final List<Integer> items = new ArrayList<>();

    public void push(int val) {
        items.add(val);
    }

    public int pop() {
        Map<Integer, Integer> counts = new HashMap<>();
        int max = 0;
        for (int v : items) {
            max = Math.max(max, counts.merge(v, 1, Integer::sum));
        }
        int idx = items.size() - 1;
        while (counts.get(items.get(idx)) != max) {
            idx--;
        }
        return items.remove(idx); // idx is an int, so this removes by position
    }
}

public class Main {
    public static void main(String[] args) {
        FreqStack fs = new FreqStack();
        for (int v : new int[]{5, 7, 5, 7, 4, 5}) {
            fs.push(v);
        }
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            out.add(fs.pop());
        }
        System.out.println(out);
    }
}

[5, 7, 5, 4]

Time: push is O(1), pop is O(n) (counting plus an ArrayList.remove(int) that shifts elements). Space: O(n).

Optimal: one stack per frequency

Keep three things: freq.get(val) (how many times val is in the stack), stacks.get(f) (the values that reached frequency f, in push order), and maxFreq.

• push(val): f = freq.get(val) + 1 (0 when absent), save it, push val onto stacks.get(f), and set maxFreq = max(maxFreq, f).
• pop(): take the top of stacks.get(maxFreq). Decrement its freq. If that stack is now empty, maxFreq--.

A value pushed three times sits in stacks.get(1), stacks.get(2) and stacks.get(3). Popping it from the top level leaves its earlier copies in the lower levels in recency order, which resolves ties.

HashMap.merge(key, 1, Integer::sum) adds one to the stored count, inserting 1 when the key is absent, and returns the new count. computeIfAbsent creates a level's stack on first use. Each level is an ArrayDeque used as a stack through push and pop. Counts are compared with != on int values: counts.get(...) returns an Integer, and Integer != int unboxes the Integer, so the comparison is by value. Comparing two Integer objects with == would compare references.

Walkthrough for push 5, 7, 5, 7, 4, 5:

stacks[1] = [5, 7, 4]
stacks[2] = [5, 7]
stacks[3] = [5]        maxFreq = 3
pop -> 5   stacks[3] empty, maxFreq = 2
pop -> 7   top of stacks[2]
pop -> 5   stacks[2] empty, maxFreq = 1
pop -> 4   top of stacks[1]

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<>();
    private final Map<Integer, Deque<Integer>> stacks = new HashMap<>();
    private int maxFreq = 0;

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

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

public class Main {
    public static void main(String[] args) {
        FreqStack fs = new FreqStack();
        for (int v : new int[]{5, 7, 5, 7, 4, 5}) {
            fs.push(v);
        }
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            out.add(fs.pop());
        }
        System.out.println(out);
    }
}

[5, 7, 5, 4]

Time: O(1) per push and pop (average, hash maps). Space: O(n).

maxFreq drops by at most one per pop: a value at level f was also pushed onto every level below it, so when level f becomes empty, level f - 1 is non-empty unless the whole structure is empty.

How to explain it in an interview

• Baseline: store a plain list; on each pop count everything, find the max frequency and remove the latest element with it. Pop is O(n).
• Key idea: give each frequency level its own stack. The top of the highest level is the answer, and push order within a level handles recency.
• Steps: (1) freq map, stacks map, maxFreq; (2) push: bump freq, push onto stacks.get(freq), update maxFreq; (3) pop: pop from stacks.get(maxFreq), decrement its freq, and if that stack is empty, maxFreq--.
• Complexity: both operations O(1) average, O(n) space.
• Common questions: a value lives in several stacks because each copy represents one push and is removed by exactly one pop. maxFreq drops by only one because every level below a non-empty level is non-empty.