Maximum Frequency Stack - Leetcode Solution

The Maximum Frequency Stack problem on Leetcode requires us to implement a stack that supports the following operations:

• Push: push an element onto the stack.
• Pop: pop the top element from the stack.
• Get max frequency: return the element with the highest frequency in the stack.

For example, if we push the elements 5, 7, 5, 2, 5, 2 onto the stack and call get max frequency, it should return 5 since it appears the most times in the stack.

One possible solution to this problem is to maintain a dictionary that maps each element to its frequency in the stack. We also need to maintain a dictionary that maps each frequency to a stack of elements that have that frequency. Lastly, we maintain a variable that keeps track of the current maximum frequency in the stack.

When we push an element onto the stack, we update its frequency in the first dictionary. We then check if the frequency of the element is greater than the current maximum frequency. If it is, we update the maximum frequency and clear the stack that holds the elements with the old maximum frequency. We then push the element onto the stack for its frequency in the second dictionary.

When we pop an element from the stack, we first retrieve its frequency from the first dictionary. We then remove the element from its frequency stack in the second dictionary. If the frequency of the element is the current maximum frequency and the stack for its frequency is empty, we decrement the maximum frequency.

When we need to get the maximum frequency element from the stack, we simply retrieve the top element from the stack that holds the elements with the current maximum frequency.

Here is the Python code implementing this solution:

class FreqStack:

    def __init__(self):
        self.freq = {}
        self.freq_stack = {}
        self.max_freq = 0

    def push(self, x: int) -> None:
        if x in self.freq:
            f = self.freq[x] + 1
        else:
            f = 1
        self.freq[x] = f
        if f > self.max_freq:
            self.max_freq = f
            self.freq_stack = {f: [x]}
        else:
            if f not in self.freq_stack:
                self.freq_stack[f] = []
            self.freq_stack[f].append(x)

    def pop(self) -> int:
        x = self.freq_stack[self.max_freq].pop()
        self.freq[x] -= 1
        if len(self.freq_stack[self.max_freq]) == 0:
            self.max_freq -= 1
        return x

    def get_max_freq(self) -> int:
        return self.freq_stack[self.max_freq][-1]

This solution has a time complexity of O(1) for all operations and a space complexity of O(n), where n is the number of elements in the stack.

1