Maximum Frequency Stack

Try to solve the Maximum Frequency Stack problem.

We'll cover the following

Statement#

Design a stack-like data structure. You should be able to push elements to this data structure and pop elements with maximum frequency.

You’ll need to implement the FreqStack class that should consist of the following:

  • Init(): This is a constructor used to declare a frequency stack.

  • Push(value): This is used to push an integer data onto the top of the stack.

  • Pop(): This is used to remove and return the most frequent element in the stack.

Note: If there is a tie for the most frequent element, then the most recently pushed element is removed and returned.

Constraints:

  • 0≤0 \leq value ≤109\leq 10^9

  • At most, 2×1032 \times 10^3 calls will be made to Push() and Pop().

  • It is guaranteed that there will be at least one element in the stack before calling Pop().

Examples#

canvasAnimation-image

1 of 2

canvasAnimation-image

2 of 2

Understand the problem#

Let’s take a moment to make sure we have correctly understood the problem. The quiz below helps us to check that we are solving precisely the right problem:

Maximum Frequency Stack

1

What is the output if four Pop() calls are made onto this stack?

A)

[5, 4, 7, 5]

B)

[5, 7, 4, 5]

C)

[7, 5, 4, 7]

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create a hash map or a dictionary to store frequencies of all elements.

Iterate over the input array and store its frequency in a hash map or dictionary. The corresponding frequency value is a stack containing all the elements with that frequency.

After all elements are pushed onto the stack, start removing the most frequent elements.

While removing elements, also decrease their frequency count from the hash map or dictionary.

When there’s a case where two or more elements have the same frequency, pop the latest element that was pushed onto the stack.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > freq_stack.py
Input #1
Input #2
Maximum Frequency Stack

Solution: Valid Anagram

Solution: Maximum Frequency Stack