⚡Flashcard Drill➔
NeetCode #375LC-895HardStackNC 250
← Back to All Problems

#375 · #895 · Maximum Frequency Stack(最大频率栈)

📌 Problem Statement & Constraints

Design a stack-like structure that pops the most frequent element. If there is a tie, the element closest to the top of the stack is popped. Implement push(val) and pop(). Constraints: 0 <= val <= 10^9; at most 2 * 10^4 calls.

💡 Core Algorithmic Approaches

  1. Keep a frequency map from value to count.
  2. Group values by frequency: groups[f] is a stack of values that have reached frequency f, in push order.
  3. Track maxf, the current maximum frequency. pop takes from groups[maxf], and since it is a stack, the most recently pushed value at that frequency comes out first -- exactly the tie-break rule.
  4. When groups[maxf] becomes empty, decrement maxf.

💻 Benchmark Python3 Implementation

class FreqStack:
    def __init__(self):
        from collections import defaultdict
        self.cnt = defaultdict(int)        # value -> frequency
        self.groups = defaultdict(list)    # frequency -> stack of values
        self.maxf = 0

    def push(self, val: int) -> None:
        self.cnt[val] += 1
        f = self.cnt[val]
        self.maxf = max(self.maxf, f)
        self.groups[f].append(val)

    def pop(self) -> int:
        v = self.groups[self.maxf].pop()   # most recent at the highest frequency
        self.cnt[v] -= 1
        if not self.groups[self.maxf]:
            self.maxf -= 1                 # that frequency bucket is now empty
        return v

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per operation.
💾 Space Complexity
O(n) for the two maps.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting by frequency on each pop: O(n log n) per call.
  • Forgetting the recency tie-break: using a set or list without order would break the "closest to the top" rule; a stack per frequency handles it.
  • Not decrementing maxf when its bucket empties: the next pop would index an empty list.
  • Decrementing the count of the wrong value: it must be the popped value.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems