Maximum frequency stack: pop the most frequent value

Build a stack of integers whose pop removes the value that occurs most often in the stack right now. When several values tie for the highest count, it removes the one whose topmost occurrence is nearest the top. Only that one occurrence is removed; everything else keeps its order.

Interface

Unless you agree on a different interface with the interviewer, assume:

• push(x: int) -> None
• pop() -> int — called only on a non-empty stack.

Example

push 5, push 7, push 5, push 7, push 4, push 5     # bottom to top: 5 7 5 7 4 5
pop()  ->  5     # 5 occurs three times
pop()  ->  7     # 5 and 7 now occur twice; the top 7 is above the top 5
pop()  ->  5     # stack is 5 7 5 4; 5 is the only value twice
pop()  ->  4     # every value once; 4 is on top

Constraints

• Up to 10^5 operations; values from -10^9 to 10^9.
• Counts only include occurrences still in the stack.

Clarifying questions

• What should pop do on an empty stack?
• Is "closest to the top" about the topmost occurrence of each tied value?
• Do we also need peek, or the current maximum frequency?

What a strong answer covers

• A count per value, plus a stack per frequency level: the value goes onto stack count after its count increases.
• pop takes from the stack of the highest frequency, decrements the count, and lowers the maximum when that stack empties.
• Why this captures recency: within one frequency level, pushes are ordered by when that level was reached.
• O(1) time per operation and O(n) space; compare with a heap keyed by (count, push time), which is O(log n).
• Tests: ties, all distinct values, one repeated value, interleaved pushes and pops.

Follow-ups

• Add peek() without removing anything.
• Break ties by the bottom-most occurrence instead.
• Support removing an arbitrary value.