Frequency Stack with Recency Tie-Breaking

Frequency Stack with Recency Tie-Breaking

Design a stack-like data structure that retrieves and removes elements based on their frequency of occurrence, breaking ties using the element's recency (LIFO order).

Implement the FreqStack class:

• FreqStack(): Initializes an empty frequency stack.
• push(val: int) -> None: Pushes an integer val onto the top of the stack.
• pop() -> int: Removes and returns the most frequent element in the stack. If there is a tie for the most frequent element, it removes and returns the element that was pushed closest to the top (i.e., the most recent one among the tied elements).

Both push and pop should operate in O(1) average time complexity.

Method Signatures

class FreqStack:
    def __init__(self):
        pass

    def push(self, val: int) -> None:
        pass

    def pop(self) -> int:
        pass

Example 1

Input:
freq_stack = FreqStack()
freq_stack.push(5)
freq_stack.push(7)
freq_stack.push(5)
freq_stack.push(7)
freq_stack.push(4)
freq_stack.push(5)
freq_stack.pop() -> returns 5
freq_stack.pop() -> returns 7
freq_stack.pop() -> returns 5
freq_stack.pop() -> returns 4

Explanation:
After pushing [5, 7, 5, 7, 4, 5]:
- Frequency map: 5 -> 3, 7 -> 2, 4 -> 1
- First pop(): 5 has the highest frequency (3). Return 5. Frequency of 5 becomes 2.
- Second pop(): Both 5 and 7 have frequency 2. 7 was pushed more recently than 5 at this frequency level. Return 7. Frequency of 7 becomes 1.
- Third pop(): 5 has frequency 2, 7 has 1, 4 has 1. 5 has highest frequency. Return 5. Frequency of 5 becomes 1.
- Fourth pop(): 7, 4, and 5 all have frequency 1. 4 is the most recent. Return 4.

Constraints

• 0 <= val <= 10^9
• At most 2 * 10^5 calls will be made to push and pop.
• It is guaranteed that pop will not be called on an empty stack.

Edge Cases to Consider

• All elements having distinct values (degenerates into a standard LIFO stack).
• Multiple elements sharing the same maximum frequency.
• A single element pushed and popped multiple times repeatedly.