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