What pattern does Maximum Frequency Stack use?

The Pattern: Stack (Frequency Grouping with Max Frequency Tracking) The Heuristic: When needing to pop the most frequent and most recent element, group elements by frequency using stacks and track the maximum frequency to achieve O(1) push and pop operations.

Maximum Frequency Stack — Monotonic Stack

Q: What is the time complexity of Maximum Frequency Stack?

O(1) amortized per push and pop operation. Each push and pop updates frequency maps and stacks in constant time, and max frequency updates occur only when frequency groups become empty or grow.

Problem

Implement a stack-like data structure that supports push and pop operations, where pop removes and returns the most frequent element; if multiple elements have the same highest frequency, pop returns the most recently pushed among them.

Calls to push and pop are valid and within reasonable limits
Values pushed are integers
pop is never called on an empty stack

Example

Input: push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop(), pop(), pop()

Output: [null, null, null, null, null, null, 5, 7, 5, 4]

The sequence of operations and their effects: 1. push(5): stack = [5] 2. push(7): stack = [5,7] 3. push(5): stack = [5,7,5] 4. push(7): stack = [5,7,5,7] 5. push(4): stack = [5,7,5,7,4] 6. push(5): stack = [5,7,5,7,4,5] 7. pop(): returns 5 because 5 is the most frequent (frequency 3), stack becomes [5,7,5,7,4] 8. pop(): returns 7 because 5 and 7 both have frequency 2, but 7 was pushed after 5, stack becomes [5,7,5,4] 9. pop(): returns 5 because 5 now has frequency 2, stack becomes [5,7,4] 10. pop(): returns 4 because 4, 7, and 5 all have frequency 1, but 4 was pushed last, stack becomes [5,7]

Approach

Straightforward Solution

A naive approach would maintain a frequency map and a global stack, scanning the entire stack to find the most frequent element on each pop. This leads to O(n) pop operations, which is inefficient for large inputs.

Core Observation

The problem requires tracking frequencies of elements and retrieving the element with the highest frequency that was most recently pushed. This combines frequency counting with stack order, demanding a data structure that supports both fast frequency updates and retrieval of the most recent element among those with maximum frequency.

Path to Optimal

Preview

The key insight is to group elements by their frequency and maintain stacks for each frequency group. This allows constant-time access to the most recent element with the highest frequency…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Maintain three components: (1) a frequency map from element to its count, (2) a map from frequency to a stack of elements with that frequency, and (3) a variable tracking the current maximum frequency…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1) amortized per push and pop operation

Each push and pop updates frequency maps and stacks in constant time, and max frequency updates occur only when frequency groups become empty or grow.

Space

O(n)

Space grows linearly with the number of pushed elements due to frequency maps and stacks storing all elements.

Solution

Python

1class FreqStack:
2    def __init__(self):
3        self.freq = {}
4        self.groups = {}
5        self.max_freq = 0
6
7    def push(self, val: int) -> None:
8        freq = self.freq.get(val, 0) + 1
9        self.freq[val] = freq
10
11        if freq not in self.groups:
12            self.groups[freq] = []
13
14        self.groups[freq].append(val)
15
16        if freq > self.max_freq:
17            self.max_freq = freq
18
19    def pop(self) -> int:
20        val = self.groups[self.max_freq].pop()
21        self.freq[val] -= 1
22
23        if not self.groups[self.max_freq]:
24            self.max_freq -= 1
25
26        return val

Step-by-Step Solution

1

Track Frequencies and Group Elements by Frequency on Push

8freq = self.freq.get(val, 0) + 1
9self.freq[val] = freq
11if freq not in self.groups:
12    self.groups[freq] = []
14self.groups[freq].append(val)
16if freq > self.max_freq:
17    self.max_freq = freq

Objective

To update the frequency count of the pushed element and add it to the stack corresponding to its new frequency, while updating the maximum frequency if necessary.

Key Insight

By incrementing the frequency of the pushed element and pushing it onto the stack for that frequency, the algorithm maintains a direct mapping from frequency to elements ordered by recency. This structure allows quick retrieval of the most recent element at any frequency. Updating max frequency ensures the algorithm knows which frequency group to pop from.

Interview Quick-Check

Core Logic

Increment the element's frequency, push it onto the corresponding frequency stack, and update max frequency if this frequency exceeds the current max.

State & Boundaries

Initialize frequency stacks lazily when a new frequency is encountered to avoid unnecessary memory usage.

Common Pitfalls & Bugs

Forgetting to update max frequency when a new highest frequency is reached leads to incorrect pop behavior.

2

Pop Most Frequent and Most Recent Element, Update Frequency and Max Frequency

To remove and return the most recent element from the stack of the current maximum frequency, decrement its frequency, and adjust the maximum frequency if the frequency stack becomes empty.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 20 Critical

val = self.groups[self.max_freq].pop()

Pop the most recent element from the stack of the current maximum frequency.

This line is the core of the algorithm: it guarantees O(1) retrieval of the element with the highest frequency and most recent insertion by leveraging the frequency-grouped stacks.

Line 4 Critical

self.groups = {}

Initialize a dictionary to map frequencies to stacks of elements.

Grouping elements by frequency in stacks allows constant-time access to the most recent element at each frequency.

Line 8 Critical

freq = self.freq.get(val, 0) + 1

Increment the frequency count for the pushed element.

Updating the frequency count is necessary to maintain accurate frequency grouping and to know which frequency stack to push the element onto.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does grouping elements by frequency and using stacks for each frequency enable O(1) pop of the most frequent and most recent element?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Maximum Frequency Stack from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Frequency Stack drill

or drill a free problem

1	`class FreqStack:`
2	`def __init__(self):`
3	`self.freq = {}`
4	`self.groups = {}`
5	`self.max_freq = 0`
6
7	`def push(self, val: int) -> None:`
8	`freq = self.freq.get(val, 0) + 1`
9	`self.freq[val] = freq`
10
11	`if freq not in self.groups:`
12	`self.groups[freq] = []`
13
14	`self.groups[freq].append(val)`
15
16	`if freq > self.max_freq:`
17	`self.max_freq = freq`
18
19	`def pop(self) -> int:`
20	`val = self.groups[self.max_freq].pop()`
21	`self.freq[val] -= 1`
22
23	`if not self.groups[self.max_freq]:`
24	`self.max_freq -= 1`
25
26	`return val`

8	`freq = self.freq.get(val, 0) + 1`
9	`self.freq[val] = freq`
11	`if freq not in self.groups:`
12	`self.groups[freq] = []`
14	`self.groups[freq].append(val)`
16	`if freq > self.max_freq:`
17	`self.max_freq = freq`