**CATEGORY: HARD**

**Problem**

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the `FreqStack`

class:

`FreqStack()`

constructs an empty frequency stack.`void push(int val)`

pushes an integer`val`

onto the top of the stack.`int 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.

**Examples**

First **Example :**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | Input ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output [null, null, null, null, null, null, null, 5, 7, 5, 4] Explanation FreqStack freqStack = new FreqStack(); freqStack.push(5); // The stack is [5] freqStack.push(7); // The stack is [5,7] freqStack.push(5); // The stack is [5,7,5] freqStack.push(7); // The stack is [5,7,5,7] freqStack.push(4); // The stack is [5,7,5,7,4] freqStack.push(5); // The stack is [5,7,5,7,4,5] freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4]. freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4]. freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4]. freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7]. |

**Constraints:**

`0 <= val <= 10`

^{9}- At most
`2 * 10`

calls will be made to^{4}`push`

and`pop`

. - It is guaranteed that there will be at least one element in the stack before calling
`pop`

.

**Solution Approach**

**Solution Logic**

In this problem of Maximum Frequency Stack, the main task is to find the frequency of the value in the stack. So, to find the frequency of the value, we use a **Map **data structure(Map <key, val>) with key as value and Val as the frequency of the number in the stack. We also consider a variable maxfreq to store the highest frequency. Initially, we initialize maxfreq to zero.

If two or more values in the stack have the same (maximum) frequency, then we have to pop the value which is close to the top of the stack. In this case, we can use the **Stack** data structure to find the top of the stack with maximum frequency. So, we maintain the mapping between frequency and stack. It denotes which element has reached this frequency in an order.

**Space Complexity: O(n)**, where n is the number of elements in the group.

**Push()**: In the push function we have to add an element to freq and group, we should also update the maxfreq value. Initially, we have to put the given integer x in freq as key and f frequency of number as Val. Integer f is calculated using the getOrDefault function if the key is a new, default value zero is taken otherwise the value will be incremented by one. Later we check whether the maxfreq value is more than the current value of f and update the value. Finally, we push the value to the group. We check whether the stack is associated with f using computeIfAbsent(). If the stack is not present it creates the stack and pushes the value x into the stack.

**Time complexity of push() : O(1)**

**Pop(): **In the pop function, we have to remove and return the top most frequent value from Stack. So, we get the most frequent element from the group, pop the element and store it in x. Since we have removed an element we update freq(key, Val) by decrementing the Val of x. Finally, we return the value of x.

**Time complexity of pop() : O(1)**

**Solution Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | class FreqStack { public FreqStack() { Map<Integer, Integer> freq = new HashMap(); Map<Integer, Stack<Integer>> group = new HashMap(); int maxfreq = 0; } public void push(int x) { int f = freq.getOrDefault(x, 0) + 1; freq.put(x, f); if (f > maxfreq) maxfreq = f; group.computeIfAbsent(f, z-> new Stack()).push(x); } public int pop() { int x = group.get(maxfreq).pop(); freq.put(x, freq.get(x) - 1); if (group.get(maxfreq).size() == 0) maxfreq--; return x; } } |

**Code Logic**

This piece of code defines a class called `FreqStack`

that represents a special stack data structure. Let me break it down in simple terms:

### Constructor `FreqStack()`

:

This is like the blueprint for creating a new `FreqStack`

object. Inside this constructor, the code does the following:

- It creates two storage containers:
`freq`

(a map to keep track of the frequency of each element) and`group`

(a map that groups elements by their frequency). - It initializes a variable
`maxfreq`

to keep track of the maximum frequency of any element.

### Method `push(int x)`

This method is used to add an element to the stack. Here’s what it does:

- It first checks how many times the element
`x`

has been pushed onto the stack and increments its frequency by 1. - It updates the
`freq`

map with the new frequency. - If the new frequency is greater than the maximum frequency seen so far, it updates
`maxfreq`

to the new frequency. - It puts the element
`x`

into a stack in the`group`

map. This stack is associated with the frequency of`x`

.

### Method `pop()`

:

This method is used to remove and return an element from the stack based on the special rules. Here’s how it works:

- It retrieves the element to pop from the stack associated with the
`maxfreq`

. This is essentially the element with the highest frequency. - It decrements the frequency of the popped element in the
`freq`

map because one occurrence has been removed. - If the stack associated with the
`maxfreq`

becomes empty (meaning there are no more elements with that frequency), it reduces the`maxfreq`

by 1. - Finally, it returns the element that was popped from the stack.

In simpler terms, this code maintains a stack of elements and keeps track of their frequencies. When you push an element onto the stack, it records how many times that element has been pushed. When you pop an element, it follows a specific rule to decide which element to pop: the one with the highest frequency. It then updates the frequency and the maximum frequency accordingly.

Leetcode Link for Maximum Frequency Stack – https://leetcode.com/problems/maximum-frequency-stack/

For more Leetcode-explained solutions visit Leetcode Solutions. If you like capture-the-flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page. Happy Leetcoding 🙂