Maximum Frequency Stack

Problem Description

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

• FreqStack() constructs an empty frequency stack.
• void push(int val) pushes an integer val onto the top of the stack.
• int pop() removes and returns the most frequent element in the stack.
  • If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

Examples

Constraints

• 0 <= val <= 10⁹
• At most 2 * 10⁴ calls will be made to push and pop.
• It is guaranteed that there are elements in the stack before calling pop.

Grouping Stacks by Frequencies

If we use a priority queue to track frequencies, push/pop operations take O(log n) time. To implement both push and pop in O(1) time, we can map frequencies to stacks. We maintain:

1. A hash map freq to count the frequency of each element.
2. A hash map group where the key is the frequency, and the value is a stack of elements that have reached that frequency.
3. An integer maxFreq to track the overall maximum frequency. When pushing val:

• Update its frequency: f = freq[val] + 1.
• Add val to group[f] (which is a stack).
• Update maxFreq = max(maxFreq, f). When popping:
• Pop from the stack at group[maxFreq].
• Decrement its frequency in freq.
• If the stack at group[maxFreq] is empty, decrement maxFreq.

Solution 1: Frequency Grouping Stacks

Map frequencies to individual element stacks to execute push and pop in O(1) time.

import java.util.HashMap;
import java.util.Stack;

class FreqStack {
    private HashMap<Integer, Integer> freq;
    private HashMap<Integer, Stack<Integer>> group;
    private int maxFreq;

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        int f = freq.getOrDefault(val, 0) + 1;
        freq.put(val, f);
        maxFreq = Math.max(maxFreq, f);

        group.putIfAbsent(f, new Stack<>());
        group.get(f).push(val);
    }

    public int pop() {
        int val = group.get(maxFreq).pop();
        freq.put(val, freq.get(val) - 1);

        if (group.get(maxFreq).isEmpty()) {
            maxFreq--; // reduce maximum frequency if current level is empty
        }
        return val;
    }
}

from collections import Counter

class FreqStack:
    def __init__(self):
        self.freq = Counter()
        self.group = {}
        self.max_freq = 0

    def push(self, val: int) -> None:
        f = self.freq[val] + 1
        self.freq[val] = f
        self.max_freq = max(self.max_freq, f)
        
        if f not in self.group:
            self.group[f] = []
        self.group[f].append(val)

    def pop(self) -> int:
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        
        if not self.group[self.max_freq]:
            self.max_freq -= 1  # reduce maximum frequency level
        return val

#include <unordered_map>
#include <stack>
#include <algorithm>

class FreqStack {
private:
    std::unordered_map<int, int> freq;
    std::unordered_map<int, std::stack<int>> group;
    int maxFreq;

public:
    FreqStack() {
        maxFreq = 0;
    }

    void push(int val) {
        int f = ++freq[val];
        maxFreq = std::max(maxFreq, f);
        group[f].push(val);
    }

    int pop() {
        int val = group[maxFreq].top();
        group[maxFreq].pop();
        freq[val]--;

        if (group[maxFreq].empty()) {
            maxFreq--;
        }
        return val;
    }
};

Complexity Analysis

• Time Complexity: O(1) for both push and pop operations since hash map lookups and stack push/pop take constant time.
• Space Complexity: O(n) auxiliary space to store elements in the frequency and grouping maps.

Where It Breaks

This solution uses considerable memory, allocating multiple stack lists. If memory constraints are tight, a priority queue is preferred, sacrificing runtime speeds (O(log n)) for better space conservation.

Common Mistakes

• Incorrect pop logic: Attempting to sort or search the frequency list during a pop operation, which raises the time complexity to O(n) and causes timeouts.
• Max frequency tracking errors: Not decrementing maxFreq when the highest frequency stack becomes empty.

Frequently Asked Questions

Why does this tie-breaker work automatically? Because each element that reaches a frequency level f is pushed onto group[f] in chronological order. Popping from group[f] naturally returns the element closest to the top of the stack first.

Can an element reside in multiple frequency stacks simultaneously? Yes. If element 5 has a frequency of 3, it will have been pushed to group[1], group[2], and group[3]. This handles its occurrences independently.

← All Problems