Maximum Frequency Stack

Maximum Frequency Stack is LeetCode problem 895, commonly asked in Amazon interviews with tags Hash Table, Stack, and Design. It requires implementing a FreqStack class that prioritizes popping the most frequent element, with ties broken by recency (closest to top).[1][7]

Problem Statement

Design a stack-like data structure called FreqStack with these operations:

• FreqStack(): Initializes an empty stack.
• void push(int val): Pushes integer val onto the top.
• int pop(): Removes and returns the most frequent element. If multiple elements share the maximum frequency, return the one closest to the top.[3][7][1]

Key Rules

When popping:

• Select the element with the highest frequency.
• For ties, choose the most recently pushed (topmost) one.
• Guaranteed at least one element exists before pop().[1][3]

Example 1

` 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:

• After pushes [5,7,5,7,4,5]: frequencies are 5:3, 7:2, 4:1.
• pop() → 5 (highest freq 3, most recent)
• Stack: [5,7,5,7,4]; freq 5:2, 7:2, 4:1
• pop() → 7 (freq 2 tie, 2nd 7 more recent)
• Stack: [5,7,5,4]; freq 5:2, 7:1, 4:1
• pop() → 5 (freq 2)
• Stack: [5,7,4]; freq 5:1, 7:1, 4:1
• pop() → 4 (freq 1 tie, most recent) `

Constraints

• 0 <= val <= 10^9
• At most 2*10^4 calls to push and pop()
• Always at least one element before pop().[7][3]