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 - LeetCode Solution

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

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. By updating the maximum frequency dynamically, the algorithm can push and pop in O(1) time.

Optimal Approach

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. On push, increment the element's frequency, push it onto the corresponding frequency stack, and update max frequency if needed. On pop, pop from the max frequency stack, decrement the element's frequency, and if the max frequency stack is empty, decrement max frequency. This ensures O(1) push and pop operations.

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

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

20val = self.groups[self.max_freq].pop()
21self.freq[val] -= 1
23if not self.groups[self.max_freq]:
24    self.max_freq -= 1
26return val

Objective

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.

Key Insight

Popping from the max frequency stack ensures the most recent element with the highest frequency is returned. Decrementing the element's frequency updates the frequency map to reflect its removal. If the max frequency stack empties, decrementing max frequency maintains correctness for subsequent pops, ensuring the algorithm always pops from the correct frequency group.

Interview Quick-Check

Core Logic

Pop from the stack corresponding to max frequency, decrement the element's frequency, and reduce max frequency if the stack becomes empty.

State & Boundaries

Ensure max frequency is decremented only when the corresponding frequency stack is empty to maintain accurate tracking.

Common Pitfalls & Bugs

Failing to decrement the element's frequency after popping leads to incorrect frequency counts and future pop errors.

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.

Line 14 Critical

self.groups[freq].append(val)

Push the element onto the stack corresponding to its frequency.

This maintains the order of elements by recency within each frequency group, enabling correct pop behavior.

Line 16 Critical

if freq > self.max_freq:

Update the maximum frequency if the current element's frequency exceeds it.

Maintaining the max frequency allows the pop operation to know which frequency group to target for removal.

Line 21 Critical

self.freq[val] -= 1

Decrement the frequency count of the popped element.

Updating the frequency map reflects the removal of one occurrence of the element, maintaining accurate frequency tracking.

Line 24 Critical

self.max_freq -= 1

Decrement the max frequency when its stack becomes empty.

Lowering max frequency ensures subsequent pops target the next highest frequency group, preserving correctness.

Line 3 Core

self.freq = {}

Initialize a dictionary to track the frequency of each element.

This frequency map is essential for knowing how many times each element has been pushed, enabling grouping by frequency.

Line 5 Core

self.max_freq = 0

Initialize a variable to track the current maximum frequency.

Tracking max frequency enables direct access to the frequency group from which to pop the most frequent element.

Line 23 Core

if not self.groups[self.max_freq]:

Check if the stack for the current max frequency is empty after popping.

Detecting an empty frequency stack signals that no elements remain at this frequency, requiring max frequency adjustment.

Line 9 Core

self.freq[val] = freq

Store the updated frequency back into the frequency map.

Persisting the updated frequency ensures subsequent operations reflect the current state of the element's frequency.

Line 11 Core

if freq not in self.groups:

Check if the frequency stack for the new frequency exists.

Lazily initializing frequency stacks prevents unnecessary memory allocation and ensures the data structure is ready to accept elements at this frequency.

Line 12 Core

self.groups[freq] = []

Create a new stack for the frequency if it does not exist.

This step ensures that each frequency has a dedicated stack to maintain insertion order of elements with that frequency.

Line 17 Core

self.max_freq = freq

Assign the new maximum frequency value.

Persisting the max frequency ensures the data structure's state is consistent for future operations.

Line 26 Core

return val

Return the popped element as the result of pop operation.

Returning the element completes the pop operation, providing the correct output as per problem requirements.

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?

Because each frequency group stack maintains elements in push order, popping from the max frequency stack returns the most recent element with that frequency, and tracking max frequency allows direct access without scanning.

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`