942. Frequency Stack
A snack machine is restocked and emptied through one chute. Build the class FrequencyStack (no constructor arguments) that holds integer item codes.
push(val)puts one more copy ofvalinto the machine.pop()removes and returns one copy of the code that currently appears the most times in the machine. If several codes tie for the highest count, remove the one whose newest copy still in the machine was pushed latest.popis only called when the machine is not empty.
Both operations must run in O(1) expected time.
Example 1
- Input:
- operations = ["FrequencyStack","push","push","push","push","push","push","pop","pop","pop","pop","pop"]arguments = [[],[14],[8],[14],[3],[8],[14],[],[],[],[],[]]
- Output:
- [null,null,null,null,null,null,null,14,8,14,3,8]
- Explanation:
14 has 3 copies so it leaves first. Then 14 and 8 both have 2 copies and the newest copy of 8 is more recent, so 8 leaves; next 14 (2 copies) leaves. Now 14, 8 and 3 have one copy each and 3 was pushed last, so 3 leaves, then 8.
Example 2
- Input:
- operations = ["FrequencyStack","push","push","push","pop","pop","pop"]arguments = [[],[5],[6],[7],[],[],[]]
- Output:
- [null,null,null,null,7,6,5]
- Explanation:
All counts are 1, so the pops follow plain last-in-first-out order.
Constraints
0 ≤ val ≤ 109
At most 3000 calls in total
pop is never called on an empty machine
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) per call
- Space
- O(n)