Leetcode 895. Maximum Frequency Stack

Problem

Leetcode 895. Maximum Frequency Stack

Example:

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
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

Approach

We can have a maxCount, and frequency to keep track of each element’s frequency count and maxCount.

We can use stack and access the most frequent, and closest to top by having its frequency as a key

Visualization of the Approach:

FreqStack freqStack = new FreqStack();
stack = {}
freq  = {}
maxCount = 0

freqStack.push(5);
stack = {1: [5]}
freq  = {5: 1}
maxCount = 1 

freqStack.push(7);
stack = {1: [5, 7]}
freq  = {5: 1, 7: 1}
maxCount = 1

freqStack.push(5);
stack = {1: [5, 7], 2: [5]}
freq  = {5: 2, 7: 1}
maxCount = 2

freqStack.push(7);
stack = {1: [5, 7], 2: [5, 7]}
freq  = {5: 2, 7: 2}
maxCount = 2

freqStack.push(4);
stack = {1: [5, 7, 4], 2: [5, 7]}
freq  = {4: 1, 5: 2, 7: 2}
maxCount = 2

freqStack.push(5);
stack = {1: [5, 7, 4], 2: [5, 7], 3: [5]}
freq  = {4: 1, 5: 3, 7: 2}
maxCount = 3

freqStack.pop();
Since stack[maxCount].pop = 5, return 5, then update all the variables
stack = {1: [5, 7, 4], 2: [5, 7]}
freq  = {4: 1, 5: 2, 7: 2}
maxCount = 2

freqStack.pop();
Since stack[maxCount].pop = 7, return 7, then update all the variables
stack = {1: [5, 7, 4], 2: [5]}
freq  = {4: 1, 5: 2, 7: 1}
maxCount = 2

freqStack.pop(); 
Since stack[maxCount].pop = 5, return 5, then update all the variables
stack = {1: [5, 7, 4]}
freq  = {4: 1, 5: 1, 7: 1}
maxCount = 1

freqStack.pop(); 
Since stack[maxCount].pop = 4, return 4, then update all the variables
stack = {1: [5, 7]}
freq  = {5: 1, 7: 1}
maxCount = 1

Here is the Python code for the solution:

class FreqStack:

    def __init__(self):
        self.stack = {}
        self.freq = {}
        self.maxCount = 0

    def push(self, val: int) -> None:
        valCount = 1 + self.freq.get(val, 0)
        self.freq[val] = valCount

        # when we encounter new maxCount, we should upate the maxCount, and add a new stack for that frequency
        if valCount > self.maxCount:  
            self.maxCount = valCount
            self.stack[valCount] = []
        
        self.stack[valCount].append(val)
    
    def pop(self) -> int:
        res = self.stack[self.maxCount].pop()
        # decrement the frequency of value
        self.freq[res] -= 1
        
        # if there's no stack with maxCount, decrement maxCount
        if not self.stack[self.maxCount]:
            self.maxCount -= 1
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(1)$ for each operation

Space Complexity: $O(n)$ for stack and hashmap