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
- Keep a frequency map from value to count.
- Group values by frequency:
groups[f]is a stack of values that have reached frequencyf, in push order. - Track
maxf, the current maximum frequency.poptakes fromgroups[maxf], and since it is a stack, the most recently pushed value at that frequency comes out first -- exactly the tie-break rule. - When
groups[maxf]becomes empty, decrementmaxf.
💻 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
maxfwhen 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.