MaxFrequencyStack

Posted: 15 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

Implement the given class FrequencyStack consisting of three functions :

FrequencyStack() : Creates a new FrequencyStack.

void push(int element) : Pushes the element onto the top of the stack.

int pop() : Returns and remove the most frequent element in the stack. If there are multiple elements with the same maximum frequency then return the integer which is closest to the stack top.

You will be given ‘q’ queries consisting of push and pop operation. In each query input is of following type :

0 : It means we have to pop the element with maximum frequency and return this element.

1 ‘element’ : It means we have to push ‘element’ onto the top of the stack. 

Note: If a pop operation is used in an empty stack nothing happens to the stack, but you have to return  -1.
Input Format :
The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains ‘q’ denoting the number of queries.

In the next 'q' lines input is either of the types :
0 : It means you have to pop the element with maximum frequency and return this element.
1 ‘element’ : It means we have to push ‘element’ onto the top of the stack. 
Output Format :
If the stack is non-empty return the removed element.
If a stack is empty return  -1.
Print the output of each test case in a new line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
0 <= q , element <= 5000
0 <= id <= 1

where 'id' denotes the type of query which is either 0 or 1.

Time Limit : 1 sec
Approach 1

Explanation: 

 

The main idea is that we are concerned with the frequency of elements. So we create hashmaps to store its frequency of elements. Now to know which element is at top corresponding to the maximum frequency we create hashmaps of a frequency corresponding to stacks. It will help us to know the top element corresponding to the maximum frequency.

 

Algorithm:

 

  • Create two hashmaps of (integer, integer),(integer, stack) and maxfreq.
  • In FrequencyStack() intialize the maxfreq to 0.
  • In the push function increase, the count of the element by 1 and corresponding to element frequency push it onto the top of the stack. If maxfreq is less than the frequency of the element then replace maxfreq by the frequency of the element.
  • In the pop function, if maxfreq is 0 then return -1(Since the stack is empty). Pop the topmost element corresponding to maxfreq stack. Decrease the frequency of the given element. If the size of the stack corresponding to the element becomes 0 after pop then decrease the maxfreq by 1.Return the element.
Try Problem