Solution
Approach 1: Stack of Stacks
Intuition
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 FreqStack
.
Algorithm
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 i
th copy of x
.
Afterwards, our goal is just to maintain freq
, group
, and maxfreq
as described above.
Complexity Analysis
-
Time Complexity: for both
push
andpop
operations. -
Space Complexity: , where
N
is the number of elements in theFreqStack
.
Analysis written by: @awice.