895. 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 integerval
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 topush
andpop
. - It is guaranteed that there will be at least one element in the stack before calling
pop
.
Solution:
By reading the question at least what you can figure is that you need to have a Map to have the frequency of all the elements. Another thing we need to have is the element which is having the maximum frequency as of now. Now to achieve that we need to have a variable to store the maximum frequency till now.
Now how we will get to know which value we need to pop and what we need to return.
Now how we will get to know which value we need to pop and what we need to return.
For that, we need to have a map<int, stack> so for each frequency, we will push that number into that stack.
For example, if the value appeared for the first time we will push it to mapOfStack[1] similarly if appeared for the second time then mapOfStack[2], and so on...
Now let'c see the code;
For example, if the value appeared for the first time we will push it to mapOfStack[1] similarly if appeared for the second time then mapOfStack[2], and so on...
Now let'c see the code;
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.