LeetCode 895. Maximum Frequency Stack

Description

https://leetcode.com/problems/maximum-frequency-stack/

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

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].

Note:

• Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
• It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
• The total number of FreqStack.push calls will not exceed 10000 in a single test case.
• The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
• The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

Explanation

keep track of the frequency, max frequency, and what are the elements of each frequency

Python Solution

class FreqStack:

    def __init__(self):
        self.frequency = collections.Counter()
        self.frequency_groups = collections.defaultdict(list)
        self.max_frequency = 0

        
    def push(self, x: int) -> None:     
        frequency = self.frequency[x] + 1
        self.frequency[x] = frequency
        
        
        if frequency > self.max_frequency:
            self.max_frequency = frequency
            
        self.frequency_groups[frequency].append(x)
        

    def pop(self) -> int:
        
        value = self.frequency_groups[self.max_frequency].pop()
        self.frequency[value] -= 1
        
        if not self.frequency_groups[self.max_frequency]:
            self.max_frequency -= 1
        
        return value

# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

• Time Complexity: ~1
• Space Complexity: ~N