895. Maximum Frequency Stack

Maximum Frequency Stack (LeetCode 895) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Stack - Min Stack Design subpattern.

• NeetCode 250 · #58 of 250 · Stack

How to solve Maximum Frequency Stack

Maximum Frequency Stack is a Min Stack Design problem, part of Stack Patterns. Design a stack that supports push, pop, top, and retrieving minimum element in constant time.

Work towards the solution in these steps:

1. Think about how you can track the frequency of each element efficiently while maintaining stack behavior.
2. Consider using a hash map to keep count of each element's frequency and another data structure to group elements by their frequency.
3. You might want to maintain multiple stacks, each representing elements of the same frequency, to quickly access the most frequent elements.

The reference solution runs in O(1) time and O(n) space.

The Maximum Frequency Stack solution and editorial walks through the full approach with reference code.

Problem statement

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class: FreqStack() constructs an empty frequency stack.

void push(int val) pushes an integer val onto the top of the stack.

int pop() removes and returns the most frequent element in the stack.

If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

Example 1: Input ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output [null, null, null, null, null, null, null, 5, 7, 5, 4] Explanation FreqStack freqStack = new FreqStack(); freqStack.push(5); // The stack is [5] freqStack.push(7); // The stack is [5,7] freqStack.push(5); // The stack is [5,7,5] freqStack.push(7); // The stack is [5,7,5,7] freqStack.push(4); // The stack is [5,7,5,7,4] freqStack.push(5); // The stack is [5,7,5,7,4,5] freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].

freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].

freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4].

freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

Constraints: 0 <= val <= 109 At most 2 104 calls will be made to push and pop.

It is guaranteed that there will be at least one element in the stack before calling pop.

Topics and companies

Topics: Hash Table, Stack.

Reported in interviews at Amazon, Microsoft, Bloomberg, Adobe.

How to practise Maximum Frequency Stack on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) time and O(n) space.

Open Maximum Frequency Stack in the code editor, or read the Maximum Frequency Stack editorial for a worked solution with its approach and complexity analysis.

Where Maximum Frequency Stack sits in the DSA pattern sheet

• Stack Patterns pattern guide
• Stack - Min Stack Design subpattern
• The full DSA patterns sheet

Problems related to Maximum Frequency Stack

Other problems that use the same Stack - Min Stack Design and Stack Patterns techniques:

• Min Stack — Medium, same subpattern
• Asteroid Collision — Medium, same pattern
• Baseball Game — Easy, same pattern
• Basic Calculator — Hard, same pattern
• Basic Calculator II — Medium, same pattern
• Basic Calculator III — Hard, same pattern

Maximum Frequency Stack FAQ