Maximum Frequency Stack

895. Maximum Frequency Stack

Average Rating: 4.73 (40 votes)

Input: ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] Output: [null,null,null,null,null,null,null,5,7,5,4] Explanation: After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then: pop() -> returns 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4]. pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4]. pop() -> returns 5. The stack becomes [5,7,4]. pop() -> returns 4. The stack becomes [5,7].

Solution
- Approach 1: Stack of Stacks

Solution

Approach 1: Stack of Stacks

Intuition

Evidently, we care about the frequency of an element. Let freq be a Map from $x$ to the number of occurrences of $x$ .

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: $O(1)$ for both push and pop operations.
Space Complexity: $O(N)$ , where N is the number of elements in the FreqStack.

Analysis written by: @awice.