Maximum Frequency Stack

HARD✓ CHIP-TIMEDLC #895 — FULL STATEMENT ↗

The drill: Build a stack where pop always returns the most frequent value pushed so far — and among values tied for most frequent, the one pushed most recently wins.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This drill builds a stack-like structure where pop doesn't simply return the most recently pushed value — it returns whichever value has been pushed the most times overall.

When two or more values are tied for the highest push count, pop favors whichever of them was pushed most recently. After a value is popped, its effective count for future comparisons drops by one.

Two operations get exercised: push, which adds a value, and pop, which removes and returns the value chosen by that frequency-then-recency rule.

EX 01

FreqStack()

push(8)

push(3)

push(8)

push(3)

push(6)

push(8)

pop() → 8

pop() → 3

pop() → 8

pop() → 6

pop() → 3

pop() → 8

FULL DRAIN THROUGH THREE TIES

EX 02

FreqStack()

push(9)

pop() → 9

ONE VALUE PUSHED THREE TIMES

EX 03

FreqStack()

push(1)

push(2)

pop() → 2

push(1)

pop() → 1

RECENCY TIEBREAK, THEN FREQUENCY TAKES OVER

operation sequence can run into the tens of thousands
pushed values can be any integer, including many duplicates
pop always favors highest frequency, then most recent push
pop is only ever called while the structure is non-empty

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A plain stack only ever answers 'what came in last?'. This one also needs 'what's come in the most?' — what would you have to track alongside every push to answer that instantly?

HINT 2 THE STRUCTURE

Every value has its own mini push-history at each frequency level it has passed through. Group pushes by the frequency they just reached, not by the value itself.

HINT 3 ONE STEP FROM THE ANSWER

Keep freq[val], a map from frequency to a stack of values that reached it, and the running maxFreq. Pop from the max-frequency bucket, decrement that value's count, and drop maxFreq only when the bucket empties.

COACH'S BOARD — THE PATTERN, STEP BY STEP

FREQUENCY BUCKETSPATTERN · FREQUENCY BUCKETSpush(1) · push(2) · pop() · push(1) · pop() · pop()

push 1

push 2

pop

push 1

pop

BUCKETS (freq → values) · maxFreq

— empty —

STEP 1

Bucket every push by the frequency it just reached. Pop always drains the top of the highest-frequency bucket.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/maximum-frequency-stack.py — RACE PACE

LANG ▸

PACE ▸

class FreqStack:
    def __init__(self):
        self.freq = collections.Counter()
        self.group = collections.defaultdict(list)  # frequency -> values that reached it, push order
        self.maxFreq = 0

    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]
        self.maxFreq = max(self.maxFreq, f)
        self.group[f].append(val)

    def pop(self) -> int:
        val = self.group[self.maxFreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxFreq]:
            self.maxFreq -= 1
        return val

TIME O(1) ALL OPSSPACE O(N)PYTHON · RACE PACE · 18 LN

class FreqStack:
    def __init__(self):
        self.items = []  # raw push history, in order

    def push(self, val: int) -> None:
        self.items.append(val)

    def pop(self) -> int:
        counts = collections.Counter(self.items)
        max_freq = max(counts.values())
        # walk backward for the most recently pushed value at max_freq
        for i in range(len(self.items) - 1, -1, -1):
            if counts[self.items[i]] == max_freq:
                return self.items.pop(i)

TIME O(N) PER POPSPACE O(N)PYTHON · TRAINING PACE · 14 LN

class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    private final Map<Integer, Deque<Integer>> group = new HashMap<>(); // frequency -> values that reached it
    private int maxFreq = 0;

    public FreqStack() {
    }

    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> bucket = group.get(maxFreq);
        int val = bucket.pop();
        freq.put(val, freq.get(val) - 1);
        if (bucket.isEmpty()) {
            maxFreq--;
        }
        return val;
    }
}

TIME O(1) ALL OPSSPACE O(N)JAVA · RACE PACE · 24 LN

class FreqStack {
    private final List<Integer> items = new ArrayList<>(); // raw push history, in order

    public FreqStack() {
    }

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

    public int pop() {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int v : items) {
            counts.merge(v, 1, Integer::sum);
        }
        int maxFreq = 0;
        for (int c : counts.values()) {
            maxFreq = Math.max(maxFreq, c);
        }
        for (int i = items.size() - 1; i >= 0; i--) {
            if (counts.get(items.get(i)) == maxFreq) {
                return items.remove(i);
            }
        }
        return -1; // unreachable given valid usage
    }
}

TIME O(N) PER POPSPACE O(N)JAVA · TRAINING PACE · 27 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED