Solution: Maximum Frequency Stack

Let's solve the Maximum Frequency Stack problem using the Knowing What to Track pattern.

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 ≤104\leq 10^4

  • 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().

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.