Code Implementation

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

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

    def pop(self) -> int:
        val = self.group[self.maxfreq].pop()
        self.freq[val] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return val
      

class FreqStack {
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> group;
    int maxfreq = 0;
public:
    FreqStack() {}
    
    void push(int val) {
        int f = ++freq[val];
        if (f > maxfreq) 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;
    }
};
      

class FreqStack {
    Map<Integer, Integer> freq;
    Map<Integer, Stack<Integer>> group;
    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);
        if (f > maxfreq) maxfreq = f;
        group.computeIfAbsent(f, z -> new Stack<>()).push(val);
    }

    public int pop() {
        int val = group.get(maxfreq).pop();
        freq.put(val, freq.get(val) - 1);
        if (group.get(maxfreq).isEmpty()) maxfreq--;
        return val;
    }
}
      

var FreqStack = function() {
    this.freq = new Map();
    this.group = new Map();
    this.maxfreq = 0;
};

FreqStack.prototype.push = function(val) {
    let f = (this.freq.get(val) || 0) + 1;
    this.freq.set(val, f);
    if (f > this.maxfreq) this.maxfreq = f;
    if (!this.group.has(f)) this.group.set(f, []);
    this.group.get(f).push(val);
};

FreqStack.prototype.pop = function() {
    let vals = this.group.get(this.maxfreq);
    let val = vals.pop();
    this.freq.set(val, this.freq.get(val) - 1);
    if (vals.length === 0) this.maxfreq--;
    return val;
};
      

Problem Description

You are asked to design a data structure called FreqStack that simulates a stack-like collection supporting two methods:

• push(val): Pushes the integer val onto the stack.
• pop(): Removes and returns the most frequent element in the stack. If there is a tie for most frequent, the element closest to the top (most recently pushed) is removed and returned.

• There will be many push and pop operations (up to 100,000).
• All values are integers in a reasonable range.
• Each pop operation is guaranteed to be valid (the stack is never empty when pop is called).

Thought Process

At first glance, this problem seems like a regular stack problem, but the twist is that we need to track the most frequent element, and in case of ties, the most recently pushed among those.

A brute-force approach might be to count the frequency of each element every time we pop, then scan the stack from top to bottom to find the most frequent and most recent element. But this would be far too slow, especially with many operations.

To improve, we realize we need:

• A way to track the frequency of each element efficiently (using a hash map).
• A way to quickly access the most recent element at the highest frequency (using stacks for each frequency).
• To keep track of the current maximum frequency.

Solution Approach

Let's break down the optimized solution step by step:

1. Track Frequencies:
   Use a hash map (dictionary) freq to record how many times each value has been pushed but not yet popped.
2. Stacks by Frequency:
   Use another hash map group where group[f] is a stack (list) of all elements with frequency f. When we push a value and its frequency increases to f, we add it to group[f].
3. Track Maximum Frequency:
   Maintain a variable maxfreq to always know the current highest frequency among elements in the stack.
4. Push Operation:
   • Increment freq[val].
   • If the new frequency is greater than maxfreq, update maxfreq.
   • Add val to group[freq[val]].
5. Pop Operation:
   • Pop from group[maxfreq] (the most recent value with highest frequency).
   • Decrement freq[val].
   • If group[maxfreq] becomes empty, decrement maxfreq.

Example Walkthrough

Let's walk through an example:

Operations:
push(5), push(7), push(5), push(7), push(4), push(5)
pop() (should return 5)
pop() (should return 7)
pop() (should return 5)
pop() (should return 4)

Step by step:

• push(5): freq[5]=1, group[1]=[5], maxfreq=1
• push(7): freq[7]=1, group[1]=[5,7], maxfreq=1
• push(5): freq[5]=2, group[2]=[5], maxfreq=2
• push(7): freq[7]=2, group[2]=[5,7], maxfreq=2
• push(4): freq[4]=1, group[1]=[5,7,4], maxfreq=2
• push(5): freq[5]=3, group[3]=[5], maxfreq=3

• pop(): group[3]=[5] → pop 5, freq[5]=2, group[3]=[], maxfreq=2
• pop(): group[2]=[5,7] → pop 7, freq[7]=1, group[2]=[5], maxfreq=2
• pop(): group[2]=[5] → pop 5, freq[5]=1, group[2]=[], maxfreq=1
• pop(): group[1]=[5,7,4] → pop 4, freq[4]=0, group[1]=[5,7], maxfreq=1

Time and Space Complexity

Brute-force approach:

• Each pop could require scanning the entire stack to find the most frequent and most recent element.
  Time: O(N) per pop (N = stack size)
• Space: O(N) for the stack

• Each push and pop only does constant-time operations: map lookups, stack push/pop, and updating maxfreq.
  Time: O(1) per operation
• Space: O(N), where N is the total number of pushed elements (for the frequency maps and group stacks)

Summary

The Maximum Frequency Stack problem is an excellent example of using multiple data structures together to achieve efficient operations. By tracking frequencies with a hash map and grouping elements by frequency in stacks, we can always access the most frequent and most recent elements in constant time. The key insight is to separate concerns: one structure for frequency, another for recency, and a simple variable for the current max frequency. This elegant combination turns a potentially slow problem into one with fast, scalable performance.