LC 0895 [H] Maximum Frequency Stack - ALawliet/algorithms GitHub Wiki

Storing (count, index, number) in max-heap and keeping map of counts. Since its a max-heap, I am negating the count and index while pushing in the heap.

The intuition is, heap will always keep the element with max count on top, and if two elements have same count, the second element (index) will be considered while doing pop operation. Also, the count map, is useful when the new occurrence of the existing element is pushed.

[FanchenBao]
February 28, 2021 4:18 PM
This is probably the most natural solution to come up with in the first attempt. I can imagine this question be asked in an interview, and a candidate shall be able to provide the heap solution in 10-20 min. Then a follow up question will be asked regarding whether the performance can be further improved. And this is the hard part, but with a bit of hint from the interviewer, such as "have you thought about a stack of stack", I expect that a candidate should be able to find the O(1) solution in another 10-20 min.
In summary, I think this is a very good question for interview.

# O(logn): max heap + hashmap of freq
class FreqStack:

    def __init__(self):
        self.maxheap = []
        self.freq = defaultdict(int)
        self.index = 0
        
    def push(self, x):
        self.freq[x] += 1
        heapq.heappush(self.maxheap, (-self.freq[x], -self.index, x))
        self.index += 1
    
    def pop(self):
        _, _, x = heapq.heappop(self.maxheap) # to be removed
        self.freq[x] -= 1
        return x

Hash map freq will count the freq of elements.
Hash map m is a map of stack.
If element x has n freq, we will push x n times in m[1], m[2] .. m[n]
maxfreq records the maximum freq.

push(x) will push x tom[++freq[x]]
pop() will pop from the m[maxfreq]

# O(1): hashmap of stacks + hashmap of freq
class FreqStack:

    def __init__(self):
        self.freq = collections.Counter() # x => freq
        self.stacks = defaultdict(list) # freq => stack of x with freq
        self.maxfreq = 0

    def push(self, x):
        self.freq[x] += 1
        self.maxfreq = max(self.maxfreq, self.freq[x])
        self.stacks[self.freq[x]].append(x)

    def pop(self):
        x = self.stacks[self.maxfreq].pop()
        if not self.stacks[self.maxfreq]: self.maxfreq -= 1
        self.freq[x] -= 1
        return x