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 ith copy of x.

Afterwards, our goal is just to maintain freq, group, and maxfreq as described above.

Complexity Analysis

  • Time Complexity: for both push and pop operations.

  • Space Complexity: , where N is the number of elements in the FreqStack.


Analysis written by: @awice.