543. Maximum Frequency Stack
Build a stack-like container that pops by how often a value occurs, not by position.
Implement a class FreqStack with two operations:
push(val)— add the integervalto the structure.pop()— remove and return the value that currently appears the most times. If several values are tied for the highest count, remove the occurrence that was pushed most recently among them, and return that value.
Every pop call is guaranteed to arrive while the structure still holds at least one element. Can you make both operations O(1)?
Example 1:
Input: push(5), push(7), push(5), push(7), push(4), push(5), then pop() four times
Output: 5, 7, 5, 4
Explanation: After the six pushes the counts are 5 → 3, 7 → 2, 4 → 1. The first pop returns 5 (highest count). Now 5 and 7 are tied at two copies each; 7 was pushed more recently, so the second pop returns 7. The third pop returns 5 (two copies beats one), and the last pop returns 4 over the remaining 5 and 7 because all three are tied at one copy and 4 sits closest to the top.
Example 2:
Input: push(1), push(2), push(3), pop(), push(1), pop(), pop()
Output: 3, 1, 2
Explanation: All of 1, 2, 3 occur once, so the first pop returns the most recent, 3. Pushing 1 again makes its count 2, so the next pop returns 1. Finally 1 and 2 each occur once and 2 is on top, so the last pop returns 2.
Constraints:
- 1 ≤ q ≤ 2 * 10⁴
- 0 ≤ val ≤ 10⁹
- pop is only called when the structure contains at least one element.
Hints:
A count per value (hash map) tells you which value is most frequent — but among tied values, how do you recover which occurrence was pushed last?
Keep a separate plain stack for every frequency level: when val reaches count f, push it onto stack number f. The top of the highest non-empty stack is always the correct answer.
When you pop from the highest stack, the value's count drops by one — it still sits in every lower stack, so no repair work is needed. Only decrease the max level when its stack empties.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: push(5), push(7), push(5), push(7), push(4), push(5), pop() × 4
Expected output: 5, 7, 5, 4