Leetcode 895. Maximum Frequency Stack

Problem

Implement a specialized stack data structure that supports two operations:

1. push(val): Add an integer value to the stack
2. pop(): Remove and return the element with the highest frequency

The key behavior: when multiple elements share the same highest frequency, return the one that was pushed most recently (closest to the top).

For instance, if you push the sequence [5, 7, 5, 7, 4, 5], the frequencies are: 5 appears 3 times, 7 appears 2 times, and 4 appears 1 time. A call to pop() should return 5 (the most frequent). After that pop, both 5 and 7 have frequency 2, but the most recently pushed instance of each matters—if 7 was pushed after the remaining instances of 5, then 7 would be popped next.

Requirements

1. Implement the FreqStack class with a constructor and two methods: push and pop
2. The push operation must add a value to the data structure
3. The pop operation must remove and return the most frequent element
4. When there are ties in frequency, the most recently pushed element among those tied elements should be returned
5. All operations should run in O(1) average time complexity

Constraints

• 1 ≤ val ≤ 10^9
• At most 2 × 10^4 calls will be made to push and pop
• It is guaranteed that there will be at least one element in the stack before calling pop
• Time complexity: O(1) for both push and pop operations
• Space complexity: O(n) where n is the number of elements

Examples

Example 1:

` Operations: freqStack.push(5) freqStack.push(7) freqStack.push(5) freqStack.push(7) freqStack.push(4) freqStack.push(5) freqStack.pop() → returns 5 freqStack.pop() → returns 7 freqStack.pop() → returns 5 freqStack.pop() → returns 4

Explanation: After all pushes: 5 has frequency 3, 7 has frequency 2, 4 has frequency 1 First pop: 5 is most frequent (freq=3) Second pop: Both 5 and 7 now have freq=2, but 7 was pushed more recently Third pop: 5 (freq=2) is now the only element with freq=2 Fourth pop: 4 (freq=1) is the last remaining `

Example 2:

` Operations: freqStack.push(1) freqStack.push(2) freqStack.push(3) freqStack.pop() → returns 3 freqStack.pop() → returns 2 freqStack.pop() → returns 1

Explanation: All elements have frequency 1, so LIFO order applies (most recent first) `

Hint 1: Tracking Frequencies You need to track two pieces of information: the frequency of each value, and which values exist at each frequency level. Consider using a hash map to count occurrences and another data structure to group values by their frequency.

Hint 2: Frequency Groups Think about organizing elements into "frequency buckets." For example, all elements with frequency 1 go in one group, all with frequency 2 in another, etc. When you pop, you take from the highest frequency bucket. How can you maintain insertion order within each bucket?

Hint 3: Maximum Frequency Tracking Keep track of the current maximum frequency seen so far. When you push an element, its frequency increases, potentially creating a new maximum. When you pop, if a frequency bucket becomes empty, you might need to decrease the maximum frequency.

Full Solution `` Explanation:

The solution uses three key data structures:

1. freq_map: A dictionary mapping each value to its current frequency count
2. freq_stacks: A dictionary mapping each frequency level to a list (stack) of values at that frequency
3. max_freq: An integer tracking the current maximum frequency

Push Operation (O(1)):

• Increment the frequency count for the pushed value
• Add the value to the stack corresponding to its new frequency level
• Update max_freq if we've created a new maximum

Pop Operation (O(1)):

• Access the stack at max_freq level and pop the most recent value (LIFO within the frequency bucket)
• Decrease the frequency count for that value in freq_map
• If the max_freq bucket is now empty, decrement max_freq

Why This Works:

The key insight is that we don't need to move elements between frequency buckets. When an element's frequency increases, we simply add another instance of it to the higher frequency bucket. When we pop, we remove from the highest frequency level and conceptually "move it back" to a lower frequency by just decrementing its count.

The recency tie-breaking happens naturally because within each frequency bucket, we use a list as a stack (LIFO), so the most recently pushed element at that frequency level is always at the end.

Time Complexity: O(1) for both push and pop operations (all operations are hash map lookups and list append/pop from end)

Space Complexity: O(n) where n is the total number of elements pushed, as we store each element once per frequency level it reaches