[LeetCode][895. Maximum Frequency Stack] HashMap Solution with Detailed Explanation
By Long Luo
This article is the solution HashMap Solution with Detailed Explanation of Problem 895. Maximum Frequency Stack.
Intuition
Let’s look at the problem description first.
 $\texttt{FreqStack()}$ constructs an empty frequency stack.
 void $\texttt{push(int val)}$ pushes an integer val onto the top of the stack.
 int $\texttt{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.
The requirements of the problems can be listed in 3 rules:
 Pop the stack by the max frequency;
 Among all the elements with the same (maximum) frequency, pop the element closest to the stack’s top.
To simplify the problem, let’s just ignore rule 2 for now, it looks easier.
Step 1
We care more about the frequency of the elements. We can use $\texttt{HashMap}$ to record the frequency of each element.
Additionally, we also care about max Frequency, the current maximum frequency of any element in the stack. we use the $\textit{maxFreq}$ to store the maximum frequency.
The code is as follows.
1  class FreqStack_map { 
This solution has a problem. If the elements with the same frequency, how to judge which element is the newest?
Step 2
How to know the order of elements with the same frequency?
We can use the stack to query this information: elements near the top of the stack are always newer.
We consider the elements with the same frequency are groups. In a group, elements were stored in the stack.
Using $\texttt{HashMap}$ combined with LinkedList, the time complexity of inserting and deleting is $O(1)$.
1  class FreqStack { 
Analysis

Time Complexity: $O(1)$.
 $\texttt{push}$: $O(1)$
 $\texttt{pop}$: $O(1)$

Space Complexity: $O(N)$.
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:)
Explore More Leetcode Solutions. 😉😃💗