Skip to main content
CodePeetCodePeet
CodePeet 250

Maximum Frequency Stack

HARDProblemSolveExternal Links

Description

Design a stack-like data structure that supports two operations: pushing an element onto the stack and popping 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 (the one pushed most recently) is removed and returned.

In other words, pop() should always remove the element that has appeared the greatest number of times among all elements currently in the stack. When two or more elements share the same highest frequency, the one that was added latest wins — mimicking stack-like recency behavior within each frequency tier.

Examples

Example 1

Input:

["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output:

[null, null, null, null, null, null, null, 5, 7, 5, 4]

Explanation:

  • FreqStack() — Create an empty frequency stack.
  • push(5) — Stack: [5]
  • push(7) — Stack: [5, 7]
  • push(5) — Stack: [5, 7, 5]
  • push(7) — Stack: [5, 7, 5, 7]
  • push(4) — Stack: [5, 7, 5, 7, 4]
  • push(5) — Stack: [5, 7, 5, 7, 4, 5]
  • pop() → returns 5. Element 5 has the highest frequency (3). After pop, stack conceptually becomes [5, 7, 5, 7, 4].
  • pop() → returns 7. Both 5 and 7 now have frequency 2, but 7 was pushed more recently (position 4 vs position 3 for the latest 5). After pop: [5, 7, 5, 4].
  • pop() → returns 5. Element 5 has frequency 2 while others have 1. After pop: [5, 7, 4].
  • pop() → returns 4. All elements have frequency 1, but 4 was pushed most recently. After pop: [5, 7].

Constraints

  • 0 ≤ 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.

Editorial

Brute Force — Sorting by Frequency and Recency

Intuition

The simplest way to solve this is to think about what pop() literally asks: find the element with the highest frequency, and among ties, pick the one that was pushed most recently.

We can maintain a list of all elements in the order they were pushed, along with a frequency counter. When pop() is called, we scan through all elements, determine which one has the maximum frequency, and among those with maximum frequency, pick the one that appears latest in the push order. Then we remove that element.

Think of it like a classroom poll. Every student writes their favorite color on a card and places it in a pile. To find the "winner," the teacher counts every card to find the most popular color. If two colors tie, the teacher picks whichever one was submitted last. This counting-every-time approach works but is slow when the pile grows large.

Step-by-Step Explanation

Let's trace through a smaller example:

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

Step 1: push(5) → elements = [(5, t=1)], freq = {5:1}

Step 2: push(7) → elements = [(5, t=1), (7, t=2)], freq = {5:1, 7:1}

Step 3: push(5) → elements = [(5, t=1), (7, t=2), (5, t=3)], freq = {5:2, 7:1}

Step 4: push(7) → elements = [(5, t=1), (7, t=2), (5, t=3), (7, t=4)], freq = {5:2, 7:2}

Step 5: push(4) → elements = [(5, t=1), (7, t=2), (5, t=3), (7, t=4), (4, t=5)], freq = {5:2, 7:2, 4:1}

Step 6: push(5) → elements = [(5, t=1), (7, t=2), (5, t=3), (7, t=4), (4, t=5), (5, t=6)], freq = {5:3, 7:2, 4:1}

Step 7: pop():

  • Scan all elements: max frequency = 3, belonging to element 5
  • Among elements with value 5, the latest was pushed at t=6 (index 5)
  • Remove it → elements = [(5, t=1), (7, t=2), (5, t=3), (7, t=4), (4, t=5)]
  • freq = {5:2, 7:2, 4:1}
  • Return 5

Step 8: pop():

  • Scan all elements: max frequency = 2, belonging to both 5 and 7
  • Latest occurrence of an element with freq 2: 7 at t=4 (index 3)
  • Why 7 and not 5? Because 7's latest push (t=4) is more recent than 5's latest push (t=3)
  • Remove it → elements = [(5, t=1), (7, t=2), (5, t=3), (4, t=5)]
  • freq = {5:2, 7:1, 4:1}
  • Return 7

Brute Force Pop — Scanning for Max Frequency Element — Watch how we scan the entire element list to find the most frequent element with the latest push timestamp, then remove it.

Algorithm

Data Structures:

  • elements: a list of (value, timestamp) pairs
  • freq: a hash map tracking the frequency of each value
  • ts: a timestamp counter incremented on each push

push(val):

  1. Increment ts
  2. Increment freq[val]
  3. Append (val, ts) to elements

pop():

  1. Find the maximum frequency across all values in freq
  2. Scan elements from right to left for the last element whose value has that max frequency
  3. Remove that element from elements
  4. Decrement freq[val]
  5. Return val

Code

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

class FreqStack {
    vector<pair<int,int>> elements; // (value, timestamp)
    unordered_map<int,int> freq;
    int ts = 0;

public:
    FreqStack() {}

    void push(int val) {
        ts++;
        freq[val]++;
        elements.push_back({val, ts});
    }

    int pop() {
        // Find max frequency
        int maxFreq = 0;
        for (auto& [key, cnt] : freq) {
            if (cnt > 0) maxFreq = max(maxFreq, cnt);
        }

        // Find rightmost element with max frequency
        int bestIdx = -1;
        for (int i = elements.size() - 1; i >= 0; i--) {
            if (freq[elements[i].first] == maxFreq) {
                bestIdx = i;
                break;
            }
        }

        int val = elements[bestIdx].first;
        elements.erase(elements.begin() + bestIdx);
        freq[val]--;
        return val;
    }
};
class FreqStack:
    def __init__(self):
        self.elements = []  # list of (value, timestamp)
        self.freq = {}      # value -> frequency
        self.ts = 0

    def push(self, val: int) -> None:
        self.ts += 1
        self.freq[val] = self.freq.get(val, 0) + 1
        self.elements.append((val, self.ts))

    def pop(self) -> int:
        # Find maximum frequency
        max_freq = max(cnt for cnt in self.freq.values() if cnt > 0)

        # Find rightmost element with max frequency
        for i in range(len(self.elements) - 1, -1, -1):
            if self.freq[self.elements[i][0]] == max_freq:
                val = self.elements[i][0]
                self.elements.pop(i)
                self.freq[val] -= 1
                return val
import java.util.*;

class FreqStack {
    private List<int[]> elements; // each entry: {value, timestamp}
    private Map<Integer, Integer> freq;
    private int ts;

    public FreqStack() {
        elements = new ArrayList<>();
        freq = new HashMap<>();
        ts = 0;
    }

    public void push(int val) {
        ts++;
        freq.put(val, freq.getOrDefault(val, 0) + 1);
        elements.add(new int[]{val, ts});
    }

    public int pop() {
        // Find max frequency
        int maxFreq = 0;
        for (int cnt : freq.values()) {
            maxFreq = Math.max(maxFreq, cnt);
        }

        // Find rightmost element with max frequency
        for (int i = elements.size() - 1; i >= 0; i--) {
            int val = elements.get(i)[0];
            if (freq.get(val) == maxFreq) {
                elements.remove(i);
                freq.put(val, freq.get(val) - 1);
                return val;
            }
        }
        return -1; // unreachable
    }
}

Complexity Analysis

Time Complexity:

  • push: O(1) — incrementing a counter and appending to a list are constant-time operations.
  • pop: O(n) — we scan the frequency map to find the max frequency (O(number of unique elements)), then scan the elements list backwards to find the rightmost element with that frequency. In the worst case, this scans all n elements. Additionally, removing from the middle of a list is O(n) due to shifting.

Space Complexity: O(n)

We store every pushed element in the elements list and maintain a frequency map. Both grow linearly with the number of push operations.

Why This Approach Is Not Efficient

Every pop() call requires scanning the entire elements list to find the maximum-frequency element, making it O(n) per pop. With up to 2×10^4 operations, a sequence of n pushes followed by n pops leads to O(n²) total work — around 4×10^8 operations in the worst case, which is too slow.

The core inefficiency is that we recompute the maximum frequency and re-scan for the best element every single time. We have no quick way to jump directly to the most frequent, most recent element.

What if we could organize elements so that the most frequent one is always immediately accessible? A heap (priority queue) gives us exactly this — it keeps the "best" element at the top, and extracting it costs only O(log n) instead of O(n).

Better Approach — Max Heap with Frequency and Timestamp

Intuition

Instead of scanning all elements during pop, we can use a max heap (priority queue) to always keep the "best" element at the top.

What makes an element the "best" for popping? Two criteria, in order:

  1. Highest frequency — the element that appears most often
  2. Most recent push — among elements tied in frequency, the one pushed latest

We can combine both criteria into a single heap entry: (-frequency, -timestamp, value). Using negative values with a min heap simulates max heap behavior. The heap automatically keeps the entry with the highest frequency (and latest timestamp among ties) at the top.

On push(val), we increment the frequency counter, increment the timestamp, and push a new tuple onto the heap. On pop(), we simply extract the top of the heap and decrement that element's frequency.

The clever part: we never remove stale entries from the heap. Old entries with outdated frequencies remain, but since we always push new entries with the current (higher) frequency, those newer entries will naturally surface to the top first. This "lazy" approach avoids the expensive operation of searching through the heap to remove outdated entries.

Step-by-Step Explanation

Let's trace through: push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop()

Step 1: push(5) — ts=1, freq={5:1}, heap push (-1, -1, 5).
Heap: [(-1,-1,5)]

Step 2: push(7) — ts=2, freq={5:1, 7:1}, heap push (-1, -2, 7).
Heap: [(-1,-2,7), (-1,-1,5)]

Step 3: push(5) — ts=3, freq={5:2, 7:1}, heap push (-2, -3, 5).
Heap: [(-2,-3,5), (-1,-1,5), (-1,-2,7)]
Note: 5's new entry with freq=2 rises to the top.

Step 4: push(7) — ts=4, freq={5:2, 7:2}, heap push (-2, -4, 7).
Heap top: (-2,-4,7) because -4 < -3 so 7 is more recent among freq-2.

Step 5: push(4) — ts=5, freq={5:2, 7:2, 4:1}, heap push (-1, -5, 4).
Heap top remains (-2,-4,7) since freq 2 > freq 1.

Step 6: push(5) — ts=6, freq={5:3, 7:2, 4:1}, heap push (-3, -6, 5).
Heap top: (-3,-6,5) — freq 3 is highest.

Step 7: pop() — Extract heap top (-3,-6,5) → val=5.
Decrement freq[5]=2. Return 5.
Old entries for 5 with freq 1 and 2 remain in heap but won't cause issues.

Step 8: pop() — Extract heap top.
Top is (-2,-4,7) → val=7. freq[7] was 2, now becomes 1. Return 7.
Why 7 before 5? Both had freq 2, but 7's timestamp (-4) beats 5's timestamp (-3) since |-4|>|-3|.

Max Heap Pop — Extracting Most Frequent, Most Recent Element — Watch how the max heap keeps the element with the highest frequency (and latest timestamp among ties) at the top for O(log n) pop operations.

Algorithm

Data Structures:

  • freq: hash map tracking current frequency of each value
  • heap: a max heap (simulated via min heap with negated values) storing tuples (-frequency, -timestamp, value)
  • ts: a monotonically increasing timestamp counter

push(val):

  1. Increment ts
  2. Increment freq[val]
  3. Push (-freq[val], -ts, val) onto the heap

pop():

  1. Extract the top element from the heap → (-f, -t, val)
  2. Decrement freq[val]
  3. Return val

Code

#include <unordered_map>
#include <queue>
using namespace std;

class FreqStack {
    unordered_map<int, int> freq;
    // Max heap: {frequency, timestamp, value}
    priority_queue<tuple<int,int,int>> heap;
    int ts = 0;

public:
    FreqStack() {}

    void push(int val) {
        ts++;
        freq[val]++;
        heap.push({freq[val], ts, val});
    }

    int pop() {
        auto [f, t, val] = heap.top();
        heap.pop();
        freq[val]--;
        return val;
    }
};
from heapq import heappush, heappop
from collections import defaultdict

class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.heap = []  # min heap with negated values
        self.ts = 0

    def push(self, val: int) -> None:
        self.ts += 1
        self.freq[val] += 1
        heappush(self.heap, (-self.freq[val], -self.ts, val))

    def pop(self) -> int:
        _, _, val = heappop(self.heap)
        self.freq[val] -= 1
        return val
import java.util.*;

class FreqStack {
    private Map<Integer, Integer> freq;
    // Max heap: compare by frequency desc, then timestamp desc
    private PriorityQueue<int[]> heap;
    private int ts;

    public FreqStack() {
        freq = new HashMap<>();
        heap = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0]; // higher freq first
            return b[1] - a[1]; // higher timestamp first
        });
        ts = 0;
    }

    public void push(int val) {
        ts++;
        freq.put(val, freq.getOrDefault(val, 0) + 1);
        heap.offer(new int[]{freq.get(val), ts, val});
    }

    public int pop() {
        int[] top = heap.poll();
        int val = top[2];
        freq.put(val, freq.get(val) - 1);
        return val;
    }
}

Complexity Analysis

Time Complexity:

  • push: O(log n) — inserting into a heap with n entries takes O(log n) time. The frequency counter update is O(1).
  • pop: O(log n) — extracting the top of a heap with n entries takes O(log n) time. The frequency decrement is O(1).

Space Complexity: O(n)

The heap stores one entry per push operation and never removes stale entries (they remain until naturally popped). With n total pushes, the heap can hold up to n entries. The frequency map holds at most m entries where m is the number of unique values (m ≤ n).

Why This Approach Is Not Efficient

While the heap approach improves pop from O(n) to O(log n), it has two drawbacks:

  1. O(log n) per operation — both push and pop involve heap operations. For 2×10^4 operations, this is fast enough, but can we do better?

  2. Heap pollution — the heap accumulates stale entries. After pushing the same value many times and popping it, old entries with outdated frequencies linger in the heap. This wastes memory and, in extreme cases with millions of operations, can degrade performance.

Is there a design that achieves O(1) for both push and pop? Yes — by rethinking how we organize elements. Instead of a global heap sorted by frequency, we can group elements by their frequency into separate stacks. The key insight is that when an element reaches frequency k, we push it onto the stack for frequency k. Popping always takes from the highest-frequency stack. Since we track max_freq and each stack is a simple list, both operations become O(1).

Optimal Approach — Frequency Group Stacks

Intuition

The breakthrough idea is to maintain a separate stack for each frequency level.

Imagine a set of shelves labeled 1, 2, 3, and so on. Each shelf holds elements that have reached that particular frequency. When you push value 5 for the first time, it goes onto shelf 1. When you push 5 again (second time), it also goes onto shelf 2. When you push 5 a third time, it goes onto shelf 3 as well.

To pop, you always look at the highest numbered shelf (max_freq) and take the top element from that shelf's stack. This automatically handles both requirements:

  • Highest frequency — you always look at the highest shelf
  • Most recent — within each shelf, the most recently added element is on top (stack behavior)

When you pop from the highest shelf and it becomes empty, you simply lower max_freq by 1. This works because if shelf k is empty, the next most frequent elements must be on shelf k-1.

Why does pushing at every frequency level work? Consider pushing 5 three times. After those pushes:

  • Shelf 1 stack has: [..., 5] (5 appeared at least once)
  • Shelf 2 stack has: [..., 5] (5 appeared at least twice)
  • Shelf 3 stack has: [5] (5 appeared three times)

When we pop from shelf 3, we get 5 and decrease its frequency to 2. Shelf 2 still correctly contains 5 — we don't need to add it. This elegant property eliminates the need for any cleanup or re-insertion.

Diagram showing frequency group stacks with shelves labeled 1, 2, 3 and elements distributed across them
Diagram showing frequency group stacks with shelves labeled 1, 2, 3 and elements distributed across them

Step-by-Step Explanation

Let's trace: push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop(), pop(), pop()

Step 1: push(5) — freq[5]=1, push 5 onto group[1]. max_freq=1.
group = {1: [5]}

Step 2: push(7) — freq[7]=1, push 7 onto group[1]. max_freq=1.
group = {1: [5, 7]}

Step 3: push(5) — freq[5]=2, push 5 onto group[2]. max_freq=2.
group = {1: [5, 7], 2: [5]}

Step 4: push(7) — freq[7]=2, push 7 onto group[2]. max_freq=2.
group = {1: [5, 7], 2: [5, 7]}

Step 5: push(4) — freq[4]=1, push 4 onto group[1]. max_freq stays 2.
group = {1: [5, 7, 4], 2: [5, 7]}

Step 6: push(5) — freq[5]=3, push 5 onto group[3]. max_freq=3.
group = {1: [5, 7, 4], 2: [5, 7], 3: [5]}

Step 7: pop() — Look at group[max_freq] = group[3] = [5]. Pop top → 5.
freq[5]=2. group[3] is now empty, so max_freq decreases to 2.
group = {1: [5, 7, 4], 2: [5, 7]}
Return 5.

Step 8: pop() — Look at group[2] = [5, 7]. Pop top → 7.
freq[7]=1. group[2] = [5], not empty, max_freq stays 2.
group = {1: [5, 7, 4], 2: [5]}
Return 7.

Step 9: pop() — Look at group[2] = [5]. Pop top → 5.
freq[5]=1. group[2] is now empty, max_freq decreases to 1.
group = {1: [5, 7, 4]}
Return 5.

Step 10: pop() — Look at group[1] = [5, 7, 4]. Pop top → 4.
freq[4]=0. group[1] = [5, 7], not empty, max_freq stays 1.
group = {1: [5, 7]}
Return 4.

Frequency Group Stacks — Push and Pop Operations — Watch how elements are pushed onto frequency-level stacks and popped from the highest-frequency stack, achieving O(1) operations.

Algorithm

Data Structures:

  • freq: hash map mapping each value to its current frequency
  • group: hash map mapping each frequency level to a stack (list) of values at that frequency
  • max_freq: integer tracking the current maximum frequency

push(val):

  1. Increment freq[val]
  2. Let f = freq[val]
  3. Append val to group[f]
  4. Update max_freq = max(max_freq, f)

pop():

  1. Pop the top element from group[max_freq] → val
  2. Decrement freq[val]
  3. If group[max_freq] is now empty, decrement max_freq
  4. Return val

Code

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

class FreqStack {
    unordered_map<int, int> freq;            // value -> frequency
    unordered_map<int, vector<int>> group;   // frequency -> stack of values
    int maxFreq = 0;

public:
    FreqStack() {}

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

    int pop() {
        int val = group[maxFreq].back();
        group[maxFreq].pop_back();
        freq[val]--;
        if (group[maxFreq].empty()) {
            maxFreq--;
        }
        return val;
    }
};
from collections import defaultdict

class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)       # value -> frequency
        self.group = defaultdict(list)     # frequency -> stack of values
        self.max_freq = 0

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

    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
        return val
import java.util.*;

class FreqStack {
    private Map<Integer, Integer> freq;           // value -> frequency
    private Map<Integer, Deque<Integer>> group;   // frequency -> stack
    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);
        group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(val);
        maxFreq = Math.max(maxFreq, f);
    }

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

Complexity Analysis

Time Complexity:

  • push: O(1) — incrementing a counter in a hash map, appending to a list, and taking the max of two integers are all constant-time operations.
  • pop: O(1) — popping from the end of a list, decrementing a counter, checking if a list is empty, and decrementing an integer are all constant-time operations.

This is the best possible time complexity for this problem — every operation runs in constant time.

Space Complexity: O(n)

Each push adds exactly one entry to exactly one frequency group stack. With n total pushes, there are n entries across all group stacks. The frequency map stores at most n entries (one per unique value). Total space: O(n).

Notably, unlike the heap approach, there are no stale entries. Every entry in every group stack represents a valid, current element — no wasted memory.