48-Frequency-Stack.md

Frequency Stack

Problem Link

https://leetcode.com/problems/maximum-frequency-stack/

---

Pattern

• Stack
• Hash Table
• Design

---

Approach

Track frequency of each value and maintain a stack for each frequency so the most frequent and most recent element is popped first.

---

Time Complexity

O(1) average per operation

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class FreqStack {
    private Map<Integer, Integer> freq = new HashMap<>();
    private Map<Integer, Stack<Integer>> group = new HashMap<>();
    private int maxFreq = 0;

    public void push(int val) {
        int f = freq.getOrDefault(val, 0) + 1;
        freq.put(val, f);
        maxFreq = Math.max(maxFreq, f);
        group.computeIfAbsent(f, k -> 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;
    }
}