MaxFrequencyStack

Hard
0/120
Average time to solve is 45m
profile
Contributed by
9 upvotes
Asked in companies
AmazonSalesforceApple

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
7
0
1 3
1 3
1 2
1 2
0
0
Sample Output 1 :
-1
 2
 3
Explanation Of Sample Input 1 :
For the First test case :

Initially, stack is empty : {}

For the first query : pop operation :
Since the stack is empty return -1.

For the second query: push operation:
The stack is now : {3}

For the third query: push operation:
The stack is now : {3,3}

For the fourth query : push operation :
Stack is now : {2,3,3}

For the fifth query : push operation :
The stack is now : {2,2,3,3}

For the sixth query : pop operation :
Both 2 and 3 have the same frequency but 2 is 
nearer to the top. Hence 2 is popped
Stack is now : {2,3,3}

For the seventh query : pop operation :
3 has a maximum frequency. Hence 3 is popped.
The stack is now : {2,3}
Sample Input 2 :
1
3
1 1
0
0
Sample Output 2 :
1
-1
Hint

Use hashmaps + stack to implement the stack.

Approaches (1)
Approach1

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.
Time Complexity

O(q) where ‘q’ is the number of queries.

 

The pop and push operation takes O(1) time. Hence total time will be O(q). Here ‘q’ is the number of queries.

Space Complexity

O(q) where ‘q’ is the number of queries.

 

To store the elements in maps. Hence it will take O(q) space. Here ‘q’ is the number of queries.

Code Solution
(100% EXP penalty)
MaxFrequencyStack
Full screen
Console