895. Maximum Frequency Stack

• solution 1: maintain val_to_frequency map and frequency_to_vals sorted map. it takes O(log N) to preserve order in frequency_to_vals
• solution 2: maintain int max_freq and frequency_to_vals collections.defaultdict(int). max_freq helps identify max frequency in O(1). to remove LRU item in list, we can use list instead of doubly linked listed here because we always remove the last element in list. We never remove a random item in the list

trick: 因为push时没有删除self.freqToInts[oldFreq], 所以pop时也不需要增加self.freqToInts[newFreq]

similar technique is used in LFU cache to identify min frequency item in O(1)

class FreqStack:

    def __init__(self):
        self.intToFreq = collections.defaultdict(int)
        c = collections.defaultdict(list)
        self.maxFreq = 0
        

    def push(self, val: int) -> None:
        newFreq = self.intToFreq[val] + 1
        self.intToFreq[val] = newFreq
        self.freqToInts[newFreq].append(val)
        self.maxFreq = max(self.maxFreq, newFreq)
        
    def pop(self) -> int:
        val = self.freqToInts[self.maxFreq].pop()
        self.intToFreq[val] -= 1
        if not self.freqToInts[self.maxFreq]:
            self.maxFreq -= 1
        return val

变种 Maximum Frequency Collection (return any element when there is a tie)

Option 1: hashmap

• O(1) put
• O(n) get

Option 2: sortedDict

• O(log N) put
• O(log N) get

Option 3: bookkeeping max freq

• O(1) put
• O(1) get