How do you approach Maximum Frequency Stack?

Track the frequency of each element with a hash map.

What is the time complexity of Maximum Frequency Stack?

Time complexity: O(1) for both push and pop. Space complexity: O(n).

What are common mistakes on Maximum Frequency Stack?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

Sitelet https://gitgood.dev/coding/maximum-frequency-stack

gitGood.dev

← Back to problems

Maximum Frequency Stack

HardData Structures

Description

Design a stack-like data structure that pushes elements and pops the most frequent element. If there is a tie for the most frequent element, the element closest to the top of the stack is popped.

Implement the following operations:

push(val) - pushes an integer val onto the stack.
pop() - removes and returns the most frequent element in the stack. If there is a tie, the element closest to the stack top is removed.

Input format: An array of commands where each command is either ["push", val] or ["pop"]. Return an array of results where push produces null and pop produces the popped value.

Example 1

Input: operations = [["push",5],["push",7],["push",5],["push",7],["push",4],["push",5],["pop"],["pop"],["pop"],["pop"]]

Output: [null,null,null,null,null,null,5,7,5,4]

Explanation: After all pushes, 5 has freq 3, 7 has freq 2, 4 has freq 1. Pop returns 5 (most frequent), then 7 (freq 2, most recent), then 5, then 4.

Constraints

- 0 <= val <= 10^9 - At most 2 * 10^4 calls to push and pop. - It is guaranteed that there will be at least one element in the stack before calling pop.

Maximum Frequency Stack: approach, complexity and pitfalls

A hard stack problem, graded against 7 test cases (5 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

Track the frequency of each element with a hash map.
Group elements by frequency - use a map from frequency to a stack of elements.
Track the current maximum frequency. Pop from the max frequency stack.

The optimal approach

Show the approach: Frequency Map + Grouped Stacks

Use a frequency map to track how many times each value appears. Use a group map that maps each frequency to a stack of values at that frequency. Track the current max frequency. On push, increment the value's frequency and push onto the corresponding frequency stack. On pop, pop from the max frequency stack, decrement frequency, and decrease maxFreq if that stack is empty.

Time: O(1) for both push and pop
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.