Frequency Stack (Max Frequency First)

🎯

Frequency Stack (Max Frequency First)

hardHEAPAmazonFacebookGoogle

Imagine a social media platform where you want to show the most frequently interacted posts first, but if two posts have the same frequency, the most recent one should appear first.

💡 This problem combines frequency counting with stack behavior, which can confuse beginners because it requires managing multiple data structures simultaneously and understanding how to prioritize elements by frequency and recency.

📋

Problem Statement

Design a stack-like data structure that supports push and pop operations. The pop operation removes and returns the element with the highest frequency. If multiple elements have the same highest frequency, pop the most recently pushed one among them. Implement the class FreqStack with methods push(int val) and pop() that behave as described.

1 ≤ number of operations ≤ 10^5Values pushed are integers in the range [0, 10^9]pop() will only be called if the stack is non-empty

💡

Example

Input"push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop(), pop(), pop()"

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

After pushing, frequencies are: 5→3, 7→2, 4→1. pop() returns 5 (highest freq), next pop returns 7 (freq 2), next pop returns 5 (freq 2 after previous pop), last pop returns 4.

• pop() called when only one element is present → returns that element
• multiple elements with same frequency pushed in different orders → pop returns most recent
• all elements have frequency 1 → pop returns most recently pushed element
• push and pop operations alternate frequently → stack maintains correct frequency and recency

⚠️

Common Mistakes

Not updating max frequency after pop

pop() returns incorrect element or crashes

✅ Check if frequency stack is empty after pop and decrement max frequency

Using a single stack without grouping by frequency

Cannot efficiently find max frequency element

✅ Use a map from frequency to stacks to group elements

Not decrementing frequency map after pop

Frequency counts become incorrect, causing wrong pops

✅ Decrement frequency of popped element in frequency map

Using a heap without timestamp or recency info

Cannot break ties correctly by recency

✅ Include timestamp or order info in heap keys

Sorting entire stack on every pop in brute force

Leads to TLE on large inputs

✅ Avoid scanning entire stack repeatedly; use frequency stacks

🧠

Brute Force (Recompute Frequencies on Each Pop)

💡 This approach exists to show the naive way of solving the problem by scanning all elements to find the max frequency and most recent element, which is inefficient but conceptually simple.

Intuition

On each pop, scan the entire stack to find the element with the highest frequency and most recent occurrence, then remove it.

Algorithm

1. Maintain a list to store pushed elements.
2. For push(val), append val to the list.
3. For pop(), count frequencies of all elements in the list.
4. Find the element with the highest frequency and most recent occurrence.
5. Remove and return that element from the list.

💡 The difficulty is realizing that scanning the entire list on every pop is very slow and not scalable.

</>

Code

class FreqStack:
    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> int:
        freq = {}
        max_freq = 0
        for v in self.stack:
            freq[v] = freq.get(v, 0) + 1
            max_freq = max(max_freq, freq[v])

        # Find most recent element with max frequency
        for i in range(len(self.stack) - 1, -1, -1):
            if freq[self.stack[i]] == max_freq:
                val = self.stack.pop(i)
                return val

# Driver code
if __name__ == '__main__':
    fs = FreqStack()
    fs.push(5)
    fs.push(7)
    fs.push(5)
    fs.push(7)
    fs.push(4)
    fs.push(5)
    print(fs.pop())  # 5
    print(fs.pop())  # 7
    print(fs.pop())  # 5
    print(fs.pop())  # 4

Line Notes

self.stack = []Initialize list to store all pushed elements in order to simulate stack behavior

self.stack.append(val)Add new element to the end simulating stack push operation

freq = {}Create frequency map to count occurrences of each element before popping

for v in self.stackCount frequencies by scanning entire stack to find max frequency

max_freq = max(max_freq, freq[v])Track highest frequency found so far during counting

for i in range(len(self.stack) - 1, -1, -1)Scan from the end to find most recent element with max frequency

if freq[self.stack[i]] == max_freqCheck if current element matches max frequency to pop

val = self.stack.pop(i)Remove and return the element found at index i

import java.util.*;

class FreqStack {
    List<Integer> stack;

    public FreqStack() {
        stack = new ArrayList<>();
    }

    public void push(int val) {
        stack.add(val);
    }

    public int pop() {
        Map<Integer, Integer> freq = new HashMap<>();
        int maxFreq = 0;
        for (int v : stack) {
            freq.put(v, freq.getOrDefault(v, 0) + 1);
            maxFreq = Math.max(maxFreq, freq.get(v));
        }
        for (int i = stack.size() - 1; i >= 0; i--) {
            if (freq.get(stack.get(i)) == maxFreq) {
                return stack.remove(i);
            }
        }
        return -1; // Should never reach here
    }

    public static void main(String[] args) {
        FreqStack fs = new FreqStack();
        fs.push(5);
        fs.push(7);
        fs.push(5);
        fs.push(7);
        fs.push(4);
        fs.push(5);
        System.out.println(fs.pop()); // 5
        System.out.println(fs.pop()); // 7
        System.out.println(fs.pop()); // 5
        System.out.println(fs.pop()); // 4
    }
}

Line Notes

List<Integer> stack;Use list to store elements in push order simulating stack

stack.add(val);Add element to the end of list to simulate push

Map<Integer, Integer> freq = new HashMap<>();Create frequency map for counting occurrences before pop

for (int v : stack)Count frequencies by iterating entire stack

maxFreq = Math.max(maxFreq, freq.get(v));Track maximum frequency found during counting

for (int i = stack.size() - 1; i >= 0; i--)Iterate backwards to find most recent max frequency element

if (freq.get(stack.get(i)) == maxFreq)Check if element matches max frequency to pop

return stack.remove(i);Remove and return the element at index i

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

class FreqStack {
    vector<int> stack;
public:
    FreqStack() {}

    void push(int val) {
        stack.push_back(val);
    }

    int pop() {
        unordered_map<int, int> freq;
        int maxFreq = 0;
        for (int v : stack) {
            freq[v]++;
            if (freq[v] > maxFreq) maxFreq = freq[v];
        }
        for (int i = (int)stack.size() - 1; i >= 0; i--) {
            if (freq[stack[i]] == maxFreq) {
                int val = stack[i];
                stack.erase(stack.begin() + i);
                return val;
            }
        }
        return -1; // Should not happen
    }
};

int main() {
    FreqStack fs;
    fs.push(5);
    fs.push(7);
    fs.push(5);
    fs.push(7);
    fs.push(4);
    fs.push(5);
    cout << fs.pop() << "\n"; // 5
    cout << fs.pop() << "\n"; // 7
    cout << fs.pop() << "\n"; // 5
    cout << fs.pop() << "\n"; // 4
    return 0;
}

Line Notes

vector<int> stack;Store elements in vector to simulate stack behavior

stack.push_back(val);Push element to the end of vector

unordered_map<int, int> freq;Map to count frequencies of elements before pop

for (int v : stack)Count frequencies by scanning entire vector

if (freq[v] > maxFreq) maxFreq = freq[v];Update max frequency found during counting

for (int i = (int)stack.size() - 1; i >= 0; i--)Scan backwards to find most recent max frequency element

stack.erase(stack.begin() + i);Remove element at index i from vector

return val;Return the popped element

class FreqStack {
    constructor() {
        this.stack = [];
    }

    push(val) {
        this.stack.push(val);
    }

    pop() {
        const freq = new Map();
        let maxFreq = 0;
        for (const v of this.stack) {
            freq.set(v, (freq.get(v) || 0) + 1);
            maxFreq = Math.max(maxFreq, freq.get(v));
        }
        for (let i = this.stack.length - 1; i >= 0; i--) {
            if (freq.get(this.stack[i]) === maxFreq) {
                return this.stack.splice(i, 1)[0];
            }
        }
    }
}

// Test
const fs = new FreqStack();
fs.push(5);
fs.push(7);
fs.push(5);
fs.push(7);
fs.push(4);
fs.push(5);
console.log(fs.pop()); // 5
console.log(fs.pop()); // 7
console.log(fs.pop()); // 5
console.log(fs.pop()); // 4

Line Notes

this.stack = []Initialize array to hold pushed elements simulating stack

this.stack.push(val)Add element to the end simulating push operation

const freq = new Map()Create map to count frequencies before pop

for (const v of this.stack)Count frequencies by iterating entire stack

maxFreq = Math.max(maxFreq, freq.get(v))Track highest frequency found during counting

for (let i = this.stack.length - 1; i >= 0; i--)Iterate backwards to find most recent max frequency element

if (freq.get(this.stack[i]) === maxFreq)Check if element matches max frequency to pop

return this.stack.splice(i, 1)[0]Remove and return the element at index i

⏱

Complexity

TimeO(n^2) in worst case because each pop scans entire stack and counts frequencies

SpaceO(n) to store all pushed elements

Each pop requires scanning the entire stack to count frequencies and find the element to pop, which is expensive for large n

💡 For n=1000 operations, this could mean up to 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Better Approach (Frequency Map + Stack per Frequency)

💡 This approach introduces a frequency map and stacks per frequency to efficiently track the most frequent and most recent elements, improving performance drastically.

Intuition

Keep track of frequency of each element and maintain stacks of elements grouped by their frequency. The highest frequency stack's top element is the next to pop.

Algorithm

1. Maintain a frequency map for each element.
2. Maintain a map from frequency to a stack of elements with that frequency.
3. Track the current maximum frequency.
4. For push(val), increment frequency, push val onto corresponding frequency stack, update max frequency.
5. For pop(), pop from max frequency stack, decrement frequency of popped element, update max frequency if needed.

💡 The key insight is grouping elements by frequency and using stacks to maintain recency within each frequency group.

</>

Code

from collections import defaultdict

class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.group = defaultdict(list)
        self.maxfreq = 0

    def push(self, val: int) -> None:
        f = self.freq[val] + 1
        self.freq[val] = f
        if f > self.maxfreq:
            self.maxfreq = 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

# Driver code
if __name__ == '__main__':
    fs = FreqStack()
    fs.push(5)
    fs.push(7)
    fs.push(5)
    fs.push(7)
    fs.push(4)
    fs.push(5)
    print(fs.pop())  # 5
    print(fs.pop())  # 7
    print(fs.pop())  # 5
    print(fs.pop())  # 4

Line Notes

self.freq = defaultdict(int)Frequency map to count occurrences of each element efficiently

self.group = defaultdict(list)Map frequency to stack of elements with that frequency to maintain recency

self.maxfreq = 0Track current maximum frequency to know which stack to pop from

f = self.freq[val] + 1Increment frequency for pushed element

self.freq[val] = fUpdate frequency map with new frequency

if f > self.maxfreqUpdate max frequency if current element frequency exceeds it

self.group[f].append(val)Push element onto stack corresponding to its frequency

val = self.group[self.maxfreq].pop()Pop most recent element from max frequency stack

self.freq[val] -= 1Decrement frequency after popping element

if not self.group[self.maxfreq]If no elements left at max frequency, decrement max frequency

import java.util.*;

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() {
        Stack<Integer> stack = group.get(maxfreq);
        int val = stack.pop();
        freq.put(val, freq.get(val) - 1);
        if (stack.isEmpty()) maxfreq--;
        return val;
    }

    public static void main(String[] args) {
        FreqStack fs = new FreqStack();
        fs.push(5);
        fs.push(7);
        fs.push(5);
        fs.push(7);
        fs.push(4);
        fs.push(5);
        System.out.println(fs.pop()); // 5
        System.out.println(fs.pop()); // 7
        System.out.println(fs.pop()); // 5
        System.out.println(fs.pop()); // 4
    }
}

Line Notes

Map<Integer, Integer> freq;Map to track frequency of each element efficiently

Map<Integer, Stack<Integer>> group;Map frequency to stack of elements to maintain recency per frequency

int maxfreq;Current maximum frequency to know which stack to pop from

int f = freq.getOrDefault(val, 0) + 1;Increment frequency for pushed element

freq.put(val, f);Update frequency map with new frequency

if (f > maxfreq) maxfreq = f;Update max frequency if needed

group.computeIfAbsent(f, z -> new Stack<>()).push(val);Push element onto frequency stack

Stack<Integer> stack = group.get(maxfreq);Get stack of elements with max frequency

int val = stack.pop();Pop most recent element from max frequency stack

freq.put(val, freq.get(val) - 1);Decrement frequency after pop

if (stack.isEmpty()) maxfreq--;Reduce max frequency if no elements left at that frequency

#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;

class FreqStack {
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> group;
    int maxfreq;
public:
    FreqStack() : maxfreq(0) {}

    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;
    }
};

int main() {
    FreqStack fs;
    fs.push(5);
    fs.push(7);
    fs.push(5);
    fs.push(7);
    fs.push(4);
    fs.push(5);
    cout << fs.pop() << "\n"; // 5
    cout << fs.pop() << "\n"; // 7
    cout << fs.pop() << "\n"; // 5
    cout << fs.pop() << "\n"; // 4
    return 0;
}

Line Notes

unordered_map<int, int> freq;Map to track frequency of each element efficiently

unordered_map<int, stack<int>> group;Map frequency to stack of elements to maintain recency per frequency

int maxfreq;Current maximum frequency to know which stack to pop from

int f = ++freq[val];Increment frequency for pushed element

if (f > maxfreq) maxfreq = f;Update max frequency if needed

group[f].push(val);Push element onto frequency stack

int val = group[maxfreq].top();Get most recent element with max frequency

group[maxfreq].pop();Pop element from frequency stack

freq[val]--;Decrement frequency after pop

if (group[maxfreq].empty()) maxfreq--;Reduce max frequency if no elements left at that frequency

class FreqStack {
    constructor() {
        this.freq = new Map();
        this.group = new Map();
        this.maxfreq = 0;
    }

    push(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);
    }

    pop() {
        const stack = this.group.get(this.maxfreq);
        const val = stack.pop();
        this.freq.set(val, this.freq.get(val) - 1);
        if (stack.length === 0) this.maxfreq--;
        return val;
    }
}

// Test
const fs = new FreqStack();
fs.push(5);
fs.push(7);
fs.push(5);
fs.push(7);
fs.push(4);
fs.push(5);
console.log(fs.pop()); // 5
console.log(fs.pop()); // 7
console.log(fs.pop()); // 5
console.log(fs.pop()); // 4

Line Notes

this.freq = new Map()Map to track frequency of each element efficiently

this.group = new Map()Map frequency to array (stack) of elements to maintain recency per frequency

this.maxfreq = 0Current maximum frequency to know which stack to pop from

let f = (this.freq.get(val) || 0) + 1Increment frequency for pushed element

this.freq.set(val, f)Update frequency map with new frequency

if (f > this.maxfreq) this.maxfreq = fUpdate max frequency if needed

if (!this.group.has(f)) this.group.set(f, [])Initialize stack for frequency if missing

this.group.get(f).push(val)Push element onto frequency stack

const val = stack.pop()Pop most recent element with max frequency

this.freq.set(val, this.freq.get(val) - 1)Decrement frequency after pop

if (stack.length === 0) this.maxfreq--Reduce max frequency if no elements left at that frequency

⏱

Complexity

TimeO(1) amortized for both push and pop operations

SpaceO(n) to store frequency maps and stacks

Each element is pushed and popped at most once per frequency level, so operations are efficient and constant time amortized

💡 For n=100000 operations, this approach can handle them efficiently within time limits.

Interview Verdict: Accepted

This is the optimal approach commonly expected in interviews for this problem.

🧠

Alternative Approach (Using Heap with Timestamp)

💡 This approach uses a max heap to always pop the element with highest frequency and most recent timestamp, demonstrating a priority queue based solution.

Intuition

Store elements in a max heap keyed by frequency and timestamp to pop the correct element efficiently.

Algorithm

1. Maintain a frequency map for each element.
2. Maintain a global timestamp counter incremented on each push.
3. Push elements into a max heap keyed by (frequency, timestamp).
4. For pop(), pop from heap, decrement frequency, and return element.

💡 The challenge is managing frequency updates and timestamps to maintain correct priority in the heap.

</>

Code

import heapq

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.heap = []
        self.time = 0

    def push(self, val: int) -> None:
        self.freq[val] = self.freq.get(val, 0) + 1
        self.time += 1
        # Use negative freq and time for max heap behavior
        heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

    def pop(self) -> int:
        freq, time, val = heapq.heappop(self.heap)
        self.freq[val] -= 1
        if self.freq[val] == 0:
            del self.freq[val]
        return val

# Driver code
if __name__ == '__main__':
    fs = FreqStack()
    fs.push(5)
    fs.push(7)
    fs.push(5)
    fs.push(7)
    fs.push(4)
    fs.push(5)
    print(fs.pop())  # 5
    print(fs.pop())  # 7
    print(fs.pop())  # 5
    print(fs.pop())  # 4

Line Notes

self.freq = {}Map to track frequency of each element

self.heap = []Heap to store elements keyed by frequency and timestamp

self.time = 0Global timestamp incremented on each push to maintain recency

self.freq[val] = self.freq.get(val, 0) + 1Increment frequency for pushed element

self.time += 1Increment timestamp for recency ordering

heapq.heappush(self.heap, (-self.freq[val], -self.time, val))Push tuple with negative freq and time for max heap behavior

freq, time, val = heapq.heappop(self.heap)Pop element with highest freq and most recent time

self.freq[val] -= 1Decrement frequency after pop

if self.freq[val] == 0: del self.freq[val]Clean up frequency map when frequency reaches zero

import java.util.*;

class FreqStack {
    Map<Integer, Integer> freq;
    PriorityQueue<int[]> heap;
    int time;

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

    public void push(int val) {
        freq.put(val, freq.getOrDefault(val, 0) + 1);
        time++;
        // Push negative freq and time for max heap behavior
        heap.offer(new int[]{-freq.get(val), -time, val});
    }

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

    public static void main(String[] args) {
        FreqStack fs = new FreqStack();
        fs.push(5);
        fs.push(7);
        fs.push(5);
        fs.push(7);
        fs.push(4);
        fs.push(5);
        System.out.println(fs.pop()); // 5
        System.out.println(fs.pop()); // 7
        System.out.println(fs.pop()); // 5
        System.out.println(fs.pop()); // 4
    }
}

Line Notes

Map<Integer, Integer> freq;Map to track frequency of each element

PriorityQueue<int[]> heap;Heap storing arrays of [freq, time, val] with max heap behavior

int time;Global timestamp incremented on each push to maintain recency

freq.put(val, freq.getOrDefault(val, 0) + 1);Increment frequency for pushed element

time++;Increment timestamp for recency ordering

heap.offer(new int[]{-freq.get(val), -time, val});Add element to heap with negative frequency and time for max heap

int[] top = heap.poll();Pop element with highest frequency and most recent time

freq.put(val, freq.get(val) - 1);Decrement frequency after pop

if (freq.get(val) == 0) freq.remove(val);Remove element from map if frequency zero

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

class FreqStack {
    unordered_map<int, int> freq;
    priority_queue<tuple<int, int, int>> heap; // freq, time, val
    int time;
public:
    FreqStack() : time(0) {}

    void push(int val) {
        freq[val]++;
        time++;
        // Push negative freq and time for max heap behavior
        heap.emplace(freq[val], time, val);
    }

    int pop() {
        auto [f, t, val] = heap.top();
        heap.pop();
        freq[val]--;
        if (freq[val] == 0) freq.erase(val);
        return val;
    }
};

int main() {
    FreqStack fs;
    fs.push(5);
    fs.push(7);
    fs.push(5);
    fs.push(7);
    fs.push(4);
    fs.push(5);
    cout << fs.pop() << "\n"; // 5
    cout << fs.pop() << "\n"; // 7
    cout << fs.pop() << "\n"; // 5
    cout << fs.pop() << "\n"; // 4
    return 0;
}

Line Notes

unordered_map<int, int> freq;Map to track frequency of each element

priority_queue<tuple<int, int, int>> heap;Max heap keyed by frequency and timestamp

int time;Global timestamp incremented on each push to maintain recency

freq[val]++;Increment frequency for pushed element

time++;Increment timestamp for recency ordering

heap.emplace(freq[val], time, val);Push tuple into heap (note: C++ priority_queue is max heap by default)

auto [f, t, val] = heap.top();Get element with highest frequency and most recent time

heap.pop();Remove element from heap

freq[val]--;Decrement frequency after pop

if (freq[val] == 0) freq.erase(val);Remove element from map if frequency zero

class FreqStack {
    constructor() {
        this.freq = new Map();
        this.heap = [];
        this.time = 0;
    }

    push(val) {
        this.freq.set(val, (this.freq.get(val) || 0) + 1);
        this.time++;
        this.heap.push({freq: this.freq.get(val), time: this.time, val});
        this.heap.sort((a, b) => b.freq - a.freq || b.time - a.time);
    }

    pop() {
        const top = this.heap.shift();
        this.freq.set(top.val, this.freq.get(top.val) - 1);
        if (this.freq.get(top.val) === 0) this.freq.delete(top.val);
        return top.val;
    }
}

// Test
const fs = new FreqStack();
fs.push(5);
fs.push(7);
fs.push(5);
fs.push(7);
fs.push(4);
fs.push(5);
console.log(fs.pop()); // 5
console.log(fs.pop()); // 7
console.log(fs.pop()); // 5
console.log(fs.pop()); // 4

Line Notes

this.freq = new Map()Map to track frequency of each element

this.heap = []Array to simulate heap (inefficient here, uses sort on every push)

this.time = 0Global timestamp incremented on each push to maintain recency

this.freq.set(val, (this.freq.get(val) || 0) + 1)Increment frequency for pushed element

this.time++Increment timestamp for recency ordering

this.heap.push({freq: this.freq.get(val), time: this.time, val})Add element with freq and time to array

this.heap.sort((a, b) => b.freq - a.freq || b.time - a.time)Sort heap to maintain max frequency and recency order (inefficient)

const top = this.heap.shift()Pop element with highest priority (max freq and most recent)

this.freq.set(top.val, this.freq.get(top.val) - 1)Decrement frequency after pop

if (this.freq.get(top.val) === 0) this.freq.delete(top.val)Remove element if frequency zero

⏱

Complexity

TimeO(log n) per push and pop due to heap operations

SpaceO(n) for frequency map and heap

Heap operations dominate complexity, slower than stack per frequency approach

💡 For large n, this approach is slower but still acceptable; sorting in JS implementation is inefficient.

Interview Verdict: Accepted but less optimal

This approach is valid but less efficient than the stack per frequency approach and may be harder to implement correctly.

📊

All Approaches - One-Glance Tradeoffs

💡 The frequency stack approach (Approach 2) is the best to code in interviews due to its optimal time and space complexity and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Frequency Map + Stack per Frequency	O(1) amortized	O(n)	No	N/A	Code this approach
3. Heap with Timestamp	O(log n)	O(n)	No	N/A	Mention as alternative, less optimal

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain tradeoffs and edge cases clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the better approach using frequency stacks.Step 4: Code the optimal solution carefully.Step 5: Test with examples and edge cases.Step 6: Discuss time and space complexity and possible follow-ups.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your ability to design efficient data structures, manage multiple maps and stacks, and handle tie-breaking by recency.

Common Follow-ups

• How to handle ties in frequency? → Use stacks per frequency to maintain recency.
• Can you optimize space usage? → Frequency stacks are already space efficient; further optimization is tricky.

💡 These follow-ups test your understanding of tie-breaking and space/time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Need to pop element with highest frequency, 2) Tie-break by most recent, 3) Frequent push/pop operations, 4) Requires efficient retrieval

Signature Phrases

pop the most frequent elementif tie, pop the most recentfrequency stack

NOT This Pattern When

Problems that only require sorting or simple stacks without frequency tracking

Similar Problems

Top K Frequent Elements - uses frequency counting and heapsDesign Twitter - uses frequency and recency for feed ordering

Practice

1. Consider the following Python code implementing the heap-based approach to find the k-th smallest pair distance. What is the returned value when calling smallestDistancePair([1,3,1], 2)?

easy

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Sort input and initialize heap

   Sorted nums = [1,1,3]. Initial heap contains pairs: (0,0,1), (2,1,2).

2. Step 2: Pop k-1=1 times and push next pairs

   Pop (0,0,1). Since j+1=2<n, push (3-1=2,0,2). Heap now: (2,0,2), (2,1,2). The smallest distance at heap top is 2.

3. Step 3: Return the k-th smallest distance

   After popping once, the top of the heap is (2,0,2), so the returned value is 2.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Second smallest pair distance is 2 [OK]

Hint: Trace heap pops and pushes carefully for small inputs [OK]

Common Mistakes:

• Off-by-one in k-1 loop
• Confusing indices i,j
• Returning wrong heap element

2. You are given a list of points on a 2D plane and need to find the k points closest to the origin (0,0). Which algorithmic approach best balances average time complexity and space usage for this problem?

easy

A. Use a Quickselect algorithm to partition points around a pivot distance until the k closest are identified.

B. Use a greedy algorithm that iteratively picks the closest point until k points are selected.

C. Use a dynamic programming approach to build up solutions for subsets of points.

D. Sort all points by their distance to the origin and return the first k points.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the k closest points efficiently, ideally better than sorting all points which is O(n log n).

2. Step 2: Identify algorithm characteristics

   Quickselect partitions points around a pivot and reduces the problem size each iteration, achieving average O(n) time and O(1) extra space, making it optimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Quickselect is known for average linear time selection problems [OK]

Hint: Quickselect offers average O(n) vs sorting's O(n log n) [OK]

Common Mistakes:

• Confusing sorting with selection algorithms
• Assuming greedy always works for closest points

3. You need to hire exactly K workers from a pool, each with a quality and a minimum wage expectation. You must pay every hired worker at least their minimum wage, and all hired workers must be paid in the same ratio to their quality. Which approach guarantees finding the minimum total cost to hire exactly K workers under these constraints?

easy

A. Use a brute force approach checking all subsets of size K and calculating total cost for each.

B. Use dynamic programming to select workers minimizing total wage while respecting quality constraints.

C. Sort workers by quality and greedily pick the first K workers with the lowest quality.

D. Sort workers by their wage-to-quality ratio, then use a max-heap or balanced tree to maintain the K smallest qualities while iterating through workers in ratio order.

Solution

1. Step 1: Understand the fairness constraint

   All hired workers must be paid at the same wage-to-quality ratio, so the maximum ratio among chosen workers determines the pay rate.

2. Step 2: Use ratio sorting and a data structure to maintain K workers

   Sorting by ratio ensures we consider possible pay rates in ascending order. Maintaining the K smallest qualities with a max-heap or balanced tree minimizes total quality sum, thus minimizing total cost = ratio * sum of qualities.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting by ratio + max-heap for qualities is the known optimal approach [OK]

Hint: Sort by ratio and maintain K smallest qualities [OK]

Common Mistakes:

• Greedy by quality only ignores wage constraints
• DP approach is not efficient or straightforward here
• Brute force is correct but not efficient

4. Suppose you want to find the kth largest element in an array where elements can be repeated and you want to find the kth largest unique element instead. Which modification to the Quickselect approach is correct?

hard

A. Use a min-heap of size k to store unique elements only, ignoring duplicates during insertion.

B. Run Quickselect as usual and then scan left and right to skip duplicates until kth unique is found.

C. Sort the array fully and iterate from largest to smallest counting unique elements until kth unique is reached.

D. Modify partition to skip duplicates and recurse only on unique elements.

Solution

1. Step 1: Understand uniqueness constraint

   Quickselect partitions by value but does not handle uniqueness inherently.

2. Step 2: Evaluate modifications

   Partial scanning or modifying partition is complex and error-prone; min-heap requires extra checks.

3. Step 3: Choose reliable approach

   Sorting fully and counting unique elements is straightforward and guarantees correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Full sort enables unique counting easily [OK]

Hint: Uniqueness requires full sort or extra data structures [OK]

Common Mistakes:

• Assuming Quickselect handles uniqueness
• Trying to modify partition without correctness
• Ignoring duplicates in heap approach

5. Suppose the problem is modified so that you can hire any number of workers (not exactly K), but you want to minimize the cost to hire at least K workers under the same fairness constraints. Which modification to the optimal algorithm is correct?

hard

A. Run the original algorithm and return the minimum cost found when the qualities list size is exactly K only.

B. Sort by quality instead of ratio and pick the first K workers to minimize cost.

C. Run the original algorithm but update the minimum cost whenever the qualities list size is at least K, not just equal to K.

D. Use a brute force approach checking all subsets of size at least K to find the minimum cost.

Solution

1. Step 1: Understand the relaxed constraint

   We want to hire at least K workers, so any group with size ≥ K is valid.

2. Step 2: Modify cost update condition

   Instead of updating min_cost only when qualities size == K, update it whenever size ≥ K to consider larger groups.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Allows considering all valid groups with size ≥ K, ensuring minimal cost [OK]

Hint: Update min cost for all sizes ≥ K, not just == K [OK]

Common Mistakes:

• Ignoring groups larger than K
• Using brute force unnecessarily
• Sorting by quality instead of ratio