# [Leetcode][895. Maximum Frequency Stack] 2-Steps to Master the HashMap Solution with Detailed Explanation

**By Long Luo**

This article is the solution of Problem 895. Maximum Frequency Stack.

1 | 895. Maximum Frequency Stack |

First, let’s look at the problem description:

$\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. 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:

1 | class FreqStack_map { |

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

1 | class FreqStack { |

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