By Long Luo

First, let’s look at the problem description:

$\texttt{FreqStack()}$ constructs an empty frequency stack.

1. void $\texttt{push(int val)}$ pushes an integer val onto the top of the stack.
2. int $\texttt{pop()}$ removes and returns the most frequent element in the stack.
3. 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. Let freq be a Map of occurrences of xx to xx.

Additionally, we also care about maxfreq, the current maximum frequency of any element in the stack. we use $\textit{maxFreq}$ to store the maximum frequency.

Code:

This solution has a problem. If 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 HashMap combined with LinkedList, the time complexity of inserting and deleting is $O(1)$.

## Analysis

• Time Complexity: $O(N)$
• 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. 😉😃💗