Stack - Maximum Frequency Stack

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.

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 <= 10⁹
At most 2 * 10⁴ 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.

Solution 1 - Using a Stack

As per the problem statement, we will have to create a stack that returns maximum frequency element, this can be achieved by using a HashMap like datastructure with key as frequency and value as Stack of elements which have the same frequency, but when we pop() elements and if there is a tie with two elements with same frequency, then the top of the stack should be popped.

So, in this approach we are going use a Map to store frequency to Stack of elements which have the same frequency, but we store such a way that we count frequency of an element as they occur, let's understand this with an example.

Say is push() operation is performed on these elements 5, 5, 7, 7, 5

When the 1^st element 5 is pushed, it's frequency is 1, so we will add it to the map under frequency 1 as key [ 1 -> 5]
Then when the 2^nd element 5 is pushed, now the frequency of 5 becomes 2, so we will add it under frequency 2 as key [[ 1 -> (5)], [ 2 -> (5)]] .
Similarly when we next elements map will look likes this [[ 1 -> (5,7)], [ 2 -> (5,7)], [ 3 -> (5)]] .
Now, if we have to pop the max frequency element, we will pop the element with frequency 3, that is 5, and the map now looks like this [[ 1 -> (5,7)], [ 2 -> (5,7)]].
Now we have a tie, there are two elements, 5 and 7, out of these two 7 pushed as last element, so we can pop the top element from the stack under the key 2, then the map looks like this [[ 1 -> (5,7)], [ 2 -> (5)]].
Now the max frequency is still 2, and if we have to pop the next max frequency element, then we can pop the top element from the stack under key 2.

For this implementation, we are also going to use another HashMap to store each elements frequency, we will use this to get frequency of an element and use that as key for the above map, and store the element into a stack under that key.

import java.util.HashMap; import java.util.Map; import java.util.Stack; public class FreqStack { final Map<Integer, Stack<Integer>> frequencyToElementsList; final Map<Integer, Integer> frequencyOfElements; int maxFrequency =0; public FreqStack() { frequencyToElementsList = new HashMap<>(); frequencyOfElements = new HashMap<>(); } public void push(int val) { int freq = frequencyOfElements.merge(val, 1, Integer::sum); if(freq>maxFrequency) { maxFrequency = freq; frequencyToElementsList.put(freq, new Stack<>()); } frequencyToElementsList.get(freq).push(val); } public int pop() { Stack<Integer> stack = frequencyToElementsList.get(maxFrequency); int result = stack.pop(); frequencyOfElements.merge(result, -1, Integer::sum); if(stack.isEmpty()) { // there are no other elements with the same frequency maxFrequency--; } return result; } public static void main(String[] args) { FreqStack freqStack = new FreqStack(); freqStack.push(5); freqStack.push(5); freqStack.push(7); freqStack.push(7); freqStack.push(5); System.out.println(freqStack.pop()); System.out.println(freqStack.pop()); System.out.println(freqStack.pop()); System.out.println(freqStack.pop()); System.out.println(freqStack.pop()); } }

Complexity Analysis:

Time complexity: Time complexity for the solution will be O(n) where n is the number of elements pushed.
Space complexity: O(n) for storing elements into stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: