Problem

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

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

**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 freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

Solution

Method 1 – Heap and HashMap

Intuition

To efficiently return the element with the highest frequency, we use a hash map to track the frequency of each element. To resolve ties (when multiple elements have the same frequency), we use a heap that prioritizes elements by frequency and, in case of a tie, by the time they were pushed (most recent first).

Approach

  1. Use a hash map to store the frequency of each element.
  2. Use a max heap (priority queue) to store nodes containing the value, its frequency, and the time it was pushed.
  3. When pushing, increment the frequency and add a node to the heap with the current time.
  4. When popping, remove the node with the highest frequency (and most recent if tied) and decrement its frequency in the hash map.

Complexity

  • ⏰ Time complexity: O(log n) for both push and pop, as each operation involves insertion or removal from the heap.
  • 🧺 Space complexity: O(n), for storing frequencies and heap nodes.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class FreqStack {
    unordered_map<int, int> freqMap;
    priority_queue<tuple<int, int, int>> pq;
    int time = 0;
public:
    void push(int x) {
        freqMap[x]++;
        pq.emplace(freqMap[x], time++, x);
    }
    int pop() {
        auto [f, t, x] = pq.top(); pq.pop();
        freqMap[x]--;
        return x;
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class FreqStack {
    private final Map<Integer, Integer> freqMap = new HashMap<>();
    private final PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.frequency == b.frequency ? b.time - a.time : b.frequency - a.frequency);
    private int time = 0;
    static class Node {
        int val, frequency, time;
        Node(int val, int frequency, int time) {
            this.val = val;
            this.frequency = frequency;
            this.time = time;
        }
    }
    public void push(int x) {
        freqMap.put(x, freqMap.getOrDefault(x, 0) + 1);
        pq.add(new Node(x, freqMap.get(x), time++));
    }
    public int pop() {
        Node node = pq.poll();
        freqMap.put(node.val, freqMap.get(node.val) - 1);
        return node.val;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import heapq
class FreqStack:
    def __init__(self) -> None:
        self.freq = {}
        self.heap = []
        self.time = 0
    def push(self, x: int) -> None:
        self.freq[x] = self.freq.get(x, 0) + 1
        heapq.heappush(self.heap, (-self.freq[x], -self.time, x))
        self.time += 1
    def pop(self) -> int:
        _, _, x = heapq.heappop(self.heap)
        self.freq[x] -= 1
        return x

Method 2 – Hashmap of Frequency and Stack

Intuition

To quickly access and remove the most frequent element, we use a hash map to track the frequency of each value and another hash map to group values by their frequency using stacks. The stack for each frequency ensures that the most recently added element with that frequency is popped first, resolving ties by recency.

Approach

  1. Maintain a hash map to count the frequency of each value.
  2. Use another hash map to map each frequency to a stack of values with that frequency.
  3. Track the current maximum frequency.
  4. On push, increment the value’s frequency, update the max frequency, and push the value onto the corresponding frequency stack.
  5. On pop, remove and return the top value from the max frequency stack, decrement its frequency, and update max frequency if needed.

Complexity

  • ⏰ Time complexity: O(1) for both push and pop, as all operations are direct hash map and stack accesses.
  • 🧺 Space complexity: O(n), for storing frequencies and stacks.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class FreqStack {
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> group;
    int maxfreq = 0;
public:
    void push(int x) {
        int f = ++freq[x];
        maxfreq = max(maxfreq, f);
        group[f].push(x);
    }
    int pop() {
        int x = group[maxfreq].top();
        group[maxfreq].pop();
        freq[x]--;
        if (group[maxfreq].empty()) maxfreq--;
        return x;
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    private final Map<Integer, Stack<Integer>> group = new HashMap<>();
    private int maxfreq = 0;
    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        maxfreq = Math.max(maxfreq, f);
        group.computeIfAbsent(f, k -> new Stack<>()).push(x);
    }
    public int pop() {
        int x = group.get(maxfreq).pop();
        freq.put(x, freq.get(x) - 1);
        if (group.get(maxfreq).isEmpty()) maxfreq--;
        return x;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class FreqStack:
    def __init__(self) -> None:
        self.freq: dict[int, int] = {}
        self.group: dict[int, list[int]] = {}
        self.maxfreq: int = 0
    def push(self, x: int) -> None:
        f = self.freq.get(x, 0) + 1
        self.freq[x] = f
        if f > self.maxfreq:
            self.maxfreq = f
        if f not in self.group:
            self.group[f] = []
        self.group[f].append(x)
    def pop(self) -> int:
        x = self.group[self.maxfreq].pop()
        self.freq[x] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return x