Max Frequency Stack LeetCode 895 — Design

LeetCode 895 Maximum Frequency Stack asks you to design a FreqStack class that supports two operations: push(val) pushes an integer val onto the stack, and pop() removes and returns the most frequent element in the stack. If there is a tie in frequency, the element closest to the top of the stack — the most recently pushed among the tied elements — is returned. For example, if you push 5, 7, 5, 7, 4, 5 in that order, the frequencies are 5→3, 7→2, 4→1. Calling pop() returns 5 because it has the highest frequency of 3. After that pop, 5→2, 7→2, 4→1. The next pop() returns 7 because 5 and 7 are tied at frequency 2 and 7 was pushed more recently than 5 among the frequency-2 layer.

The challenge is achieving O(1) time complexity for both push and pop. With up to 2*10^4 calls and values up to 10^8, any solution that scans all elements or uses a heap with lazy deletion in O(log n) per operation is technically possible but misses the point. The problem is designed to test whether you can recognize that grouping elements by frequency into separate stacks naturally handles both the frequency-maximization and the recency tie-breaking in constant time.

This problem appears in FAANG interviews as a test of data structure creativity. The elegant solution requires two insight leaps: first, that you need to track frequency per value rather than globally, and second, that rather than sorting or heaping by frequency you simply maintain one stack per frequency level and track the current maximum frequency separately.

The instinct when you see "return the most frequent element" is to reach for a max-heap keyed by frequency. You could maintain a heap where each entry stores (frequency, push_timestamp, value), and pop the heap to get the most frequent — with ties broken by the largest timestamp (most recent push). This approach is conceptually correct and gives you the right answer.

The problem is time complexity. A heap gives O(log n) push and O(log n) pop, not O(1). When you push a value that already exists, you need to update its entry in the heap — heap update is O(log n) with a standard binary heap because you must find the element first. You can work around this with lazy deletion: mark old entries as stale and skip them on pop, but this bloats the heap and still costs O(log n) amortized per operation. For an interview that explicitly asks for O(1), the heap is the wrong tool.

A second structural issue is that the heap approach conflates the frequency tracking and the recency tracking into a single key tuple. When multiple elements share the same frequency, you need a secondary sort by recency. Managing this correctly with lazy deletion becomes error-prone. The two-map solution completely sidesteps these problems by making frequency stacks do the recency tracking automatically — the most recently pushed element at a given frequency is simply the top of that frequency's stack.

The solution uses two hash maps and one integer. The first map, freqMap, maps each value to its current frequency — how many times that value has been pushed without a corresponding pop removing it. Initially empty, freqMap grows as values are pushed and shrinks (frequencies decrement) as values are popped. The second map, groupMap, maps each frequency integer to a stack (list in Python) of values that currently have exactly that frequency. Initially empty, groupMap gains entries as push adds elements to frequency layers.

The integer maxFreq tracks the current maximum frequency across all pushed elements. It starts at 0 and is updated on push: after incrementing freqMap[val], if the new frequency exceeds maxFreq, update maxFreq. On pop, maxFreq may decrease: after popping from groupMap[maxFreq], if that stack becomes empty, decrement maxFreq by 1. Crucially, maxFreq can only decrease by 1 on each pop — you cannot jump from maxFreq=5 to maxFreq=3 in a single pop because each pop removes one element from the current max-frequency layer, which means at most one level collapses.

The elegance of this design is that an element at frequency f also exists implicitly at all lower frequency levels. When you push val for the third time (so freqMap[val] goes from 2 to 3), you add val to groupMap[3]. But val also remains in groupMap[2] and groupMap[1] from its earlier pushes. This is intentional. When val is popped at frequency 3, it is removed from groupMap[3] and freqMap[val] decrements to 2 — it is now correctly accessible at groupMap[2] for the next pop that needs frequency-2 elements. The lower-frequency stacks act as a history of the element's push sequence.

The push(val) operation has three steps, all O(1). First, increment freqMap[val] by 1. If val is not yet in freqMap, initialize it to 0 before incrementing (or use defaultdict(int) in Python which initializes to 0 automatically). After this step, freqMap[val] holds the new frequency of val — call it f.

Second, append val to groupMap[f]. This records that val has been pushed to frequency level f, and positions it as the most recent element at that frequency. If groupMap[f] does not exist yet, initialize it as an empty list or stack before appending. In Python with defaultdict(list), this is automatic. In Java, you must check if the key f exists in groupMap and create a new Stack if not: groupMap.putIfAbsent(f, new Stack<>()).

Third, update maxFreq: set maxFreq = max(maxFreq, f). Since f is the new frequency of val and frequencies only increase by 1 per push, f can be at most maxFreq + 1. If f equals maxFreq + 1, then val is the new most-frequent element and maxFreq must advance. If f is less than or equal to maxFreq, the maximum does not change. All three steps are O(1) hash map and integer operations.

The pop() operation has four steps, all O(1). First, pop the top element from groupMap[maxFreq]. Call this element val. This is the most recently pushed element at the current maximum frequency — exactly what the problem requires. In Python this is groupMap[maxFreq].pop(). In Java this is groupMap.get(maxFreq).pop().

Second, decrement freqMap[val] by 1. This reflects that val is now at a lower frequency in the data structure. Its next appearance in groupMap will be at frequency freqMap[val] (the decremented value). If freqMap[val] reaches 0, you can optionally delete the key from freqMap to save space, though it is not required for correctness.

Third, check if groupMap[maxFreq] is now empty. If the stack at maxFreq has no more elements, no element currently has that frequency, so decrement maxFreq by 1. This is the only case where maxFreq decreases. If groupMap[maxFreq] still has elements, maxFreq stays the same — there are other elements with the same maximum frequency waiting to be returned by future pop calls. Fourth, return val.

The Python implementation uses defaultdict for clean initialization. In __init__, set self.freqMap = defaultdict(int) and self.groupMap = defaultdict(list) and self.maxFreq = 0. The push method: self.freqMap[val] += 1; f = self.freqMap[val]; self.groupMap[f].append(val); self.maxFreq = max(self.maxFreq, f). The pop method: val = self.groupMap[self.maxFreq].pop(); self.freqMap[val] -= 1; if not self.groupMap[self.maxFreq]: self.maxFreq -= 1; return val. The entire class is about 10 lines. Both push and pop are O(1) amortized. Space is O(n) where n is the total number of push calls.

The Java implementation uses HashMap with explicit initialization. In the constructor: freqMap = new HashMap<>(); groupMap = new HashMap<>(); maxFreq = 0. The push method: int f = freqMap.getOrDefault(val, 0) + 1; freqMap.put(val, f); groupMap.putIfAbsent(f, new Stack<>()); groupMap.get(f).push(val); if (f > maxFreq) maxFreq = f. The pop method: int val = groupMap.get(maxFreq).pop(); freqMap.put(val, freqMap.get(val) - 1); if (groupMap.get(maxFreq).isEmpty()) maxFreq--; return val. O(1) for both operations, O(n) space.

A subtle correctness point: you should not clean up old groupMap entries when a frequency stack becomes empty during pop. The only action needed is decrementing maxFreq. If you also delete groupMap[maxFreq], you lose history for values at lower frequencies. Similarly, do not delete freqMap entries when a value's frequency hits 0 unless you add a null check before accessing it again — the defaultdict(int) in Python handles this safely, but in Java you must use getOrDefault.

LFU Cache (LeetCode 460) is the closest relative of this problem. LFU Cache evicts the least frequently used key when capacity is exceeded, with ties broken by least recently used. The solution uses exactly the same two-map structure: a key-to-frequency map and a frequency-to-ordered-dict (or doubly linked list) of keys at each frequency, plus a minFreq tracker. The symmetry with Maximum Frequency Stack is striking — LFU minimizes frequency while FreqStack maximizes it, but both use per-frequency grouping with a single integer tracker updated in O(1).

Min Stack (LeetCode 155) is a simpler design problem in the same family. It asks for a stack that supports push, pop, top, and getMin in O(1). The solution uses an auxiliary stack that tracks the running minimum at each level. Like Maximum Frequency Stack, the key insight is maintaining auxiliary state alongside the main data structure so that each query is O(1) rather than requiring a scan.

Design Twitter (LeetCode 355), Design Add and Search Words (LeetCode 211), and the broader stack design family — including Next Greater Element and Daily Temperatures — all test your ability to augment a basic data structure with extra bookkeeping. The lesson from LeetCode 895 generalizes: when a problem asks you to efficiently query a property of the "best" element (most frequent, least frequent, minimum, maximum), look for a way to maintain that property incrementally rather than recomputing it from scratch on each query.