895. Max Frequency Stack

Maximum Frequency Stack

The key to this type of problem usually is understanding what pop() is supposed to do.

We need to remove and return the element with the highest frequency in stack.

If multiple elements tie for highest frequency, pick the one closest to stack top, meaning the one that was pushed into most recently.

So we need to maintain a stack structure per frequency level, ensuring that under a tiebreaker, the most recently added element is retrieved.

Stack of Stacks

Architecture

(1). Frequency Stack: outer structure. Whenever current highest frequency has all its elements removed, that frequency is no longer maximum.

It gets popped off the outer stack, letting next frequency take over outer stack top.

(2). Element Stack: inner structure. Each frequency has its own element stack.

Among elements at the same frequency, the one that most recently reached this frequency is at its inner stack top.

This is exactly the tiebreaker of our problem.

So we maintain a frequencyStack as outer stack, where index $i$ represents frequency $i$.

Each frequency $i$ has its own inner stack storing all elements currently at that frequency.

Method Implementation

I. push(int value): when called, first increment value's frequency in hash map.

Say the updated frequency is $x$.

Find the inner stack at index $x$ in outer stack and push value to inner stack top.

If $x$ equals current length of outer stack, it means outer stack only reflects up to frequency $x - 1$.

A new inner stack must be created at outer stack top to store frequency $x$.

II. pop(): each time it's called, locate outer stack top, at which there is an inner stack.

Pop the top element from this inner stack.

Decrement that popped element's frequency in hash table.

This gives us the most recently pushed element among those with highest frequency.

Then check if that popped element's inner stack is now empty.

If so, pop that inner stack off outer stack as well, accurately reflecting correct maximum frequency.

C++

#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

class MaxFrequencyStack // LeetCode Q.895.
{
private:
    // Each idx contains stack of values with frequency = idx.
    // Pad empty stack to adjust for 0-based indexing.
    vector<stack<int>> frequencyStack = {{}};

    unordered_map<int, int> valuesFrequencies;

public:
    MaxFrequencyStack() {}

    void push(int value) {
        valuesFrequencies[value]++;
        int frequency = valuesFrequencies[value];

        // Need to add another stack for current frequency.
        if (frequency == frequencyStack.size())
            frequencyStack.push_back({});

        frequencyStack[frequency].push(value);
    }

    int pop() {
        int mostFreqValue = frequencyStack.back().top();
        valuesFrequencies[mostFreqValue]--;

        frequencyStack.back().pop();
        if (frequencyStack.back().empty())
            frequencyStack.pop_back();

        return mostFreqValue;
    }
};

Python

class MaxFrequencyStack:  # LeetCode Q.895.
    def __init__(self):
        self.vals_freqs: dict[int, int] = dict()

        # Each idx contains stack of values w/ frequency = idx.
        # Pad empty stack to adjust for 0-based indexing.
        self.freqs_stacks: list[list[int]] = [[]]
    
    def push(self, value: int) -> None:
        if value not in self.vals_freqs.keys():
            self.vals_freqs.update({value: 0})
        self.vals_freqs[value] += 1

        # Need to add another stack for current frequency.
        if self.vals_freqs[value] == len(self.freqs_stacks):
            self.freqs_stacks.append([])

        frequency = self.vals_freqs[value]
        self.freqs_stacks[frequency].append(value)

    def pop(self) -> int:
        most_freq_val = self.freqs_stacks[-1].pop(-1)

        if not self.freqs_stacks[-1]: self.freqs_stacks.pop(-1)

        self.vals_freqs[most_freq_val] -= 1
        return most_freq_val

Both push(int value) and pop() run in $O(1)$ time. Space is $O(n)$.

Don't use heaps like Algo Monster and end up with $O(\log n)$ time complexity.