Approach 1: Stack of Stacks
Evidently, we care about the frequency of an element. Let
freq be a
Map from to the number of occurrences of .
Also, we (probably) care about
maxfreq, the current maximum frequency of any element in the stack. This is clear because we must pop the element with the maximum frequency.
The main question then becomes: among elements with the same (maximum) frequency, how do we know which element is most recent? We can use a stack to query this information: the top of the stack is the most recent.
To this end, let
group be a map from frequency to a stack of elements with that frequency. We now have all the required components to implement
Actually, as an implementation level detail, if
x has frequency
f, then we'll have
x in all
group[i] (i <= f), not just the top. This is because each
group[i] will store information related to the
ith copy of
Afterwards, our goal is just to maintain
maxfreq as described above.
Time Complexity: for both
Space Complexity: , where
Nis the number of elements in the