Maximum Frequency Stack

Maximum Frequency Stack 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.

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

Problems related to Maximum Frequency Stack

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

Preparing this workspace.