By Long Luo

Intuition

Let’s look at the problem description first.

1. $\texttt{FreqStack()}$ constructs an empty frequency stack.
2. void $\texttt{push(int val)}$ pushes an integer val onto the top of the stack.
3. int $\texttt{pop()}$ removes and returns the most frequent element in the stack.
4. 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:

1. Pop the stack by the max frequency;
2. 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.

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)$.

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. 😉😃💗