Maximum Frequency Stack - Practice Coding Problems

Maximum Frequency Stack - 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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"], values = [null, 5, 7, 5, 7, 4, 5, null, null, null, null]

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

💡 Note: After pushes: 5(freq=3), 7(freq=2), 4(freq=1). Pop returns most frequent: 5, then 7, then 5, then 4.

Example 2 — Tie Breaking

$ Input: operations = ["FreqStack", "push", "push", "push", "pop", "pop"], values = [null, 1, 2, 3, null, null]

› Output: [null, null, null, null, 3, 2]

💡 Note: All elements have frequency 1, so pop returns most recent: 3, then 2.

Example 3 — Same Element Multiple Times

$ Input: operations = ["FreqStack", "push", "push", "pop", "pop"], values = [null, 1, 1, null, null]

› Output: [null, null, null, 1, 1]

💡 Note: Push 1 twice (freq=2), pop returns 1 (freq becomes 1), pop returns 1 again.

Constraints

1 ≤ val ≤ 10⁹
At most 2 × 10⁴ calls to push and pop
It is guaranteed that there will be at least one element in the stack before calling pop

Visualization

Tap to expand

Understanding the Visualization

Input

Push operations: 5, 7, 5, 7, 4, 5

Process

Track frequencies and organize in frequency stacks

Output

Pop most frequent elements: 5, 7, 5, 4

Key Takeaway

🎯 Key Insight: Group elements by frequency in separate stacks for instant O(1) access to maximum frequency elements

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to group elements by frequency in separate stacks, enabling O(1) operations. Best approach uses frequency map with frequency-level stacks. Time: O(1), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Linear Search	O(n)	O(n)	Store all elements and scan entire structure for most frequent on each pop
Frequency Map with Stacks	O(1)	O(n)	Use frequency counter and group elements by frequency level in separate stacks

Brute Force with Linear Search — Algorithm Steps

Store elements in order with frequency map
On pop: scan all elements to find max frequency
Among max frequency elements, pick the last inserted

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Elements

Keep all elements with their frequencies

Scan for Max

Linear search to find maximum frequency

Pick Latest

Among ties, choose the most recent

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *elements;
    int *orders;
    int *freq;
    int size;
    int capacity;
    int order;
} FreqStack;

FreqStack* freqStackCreate() {
    FreqStack* fs = malloc(sizeof(FreqStack));
    fs->capacity = 1000;
    fs->elements = malloc(fs->capacity * sizeof(int));
    fs->orders = malloc(fs->capacity * sizeof(int));
    fs->freq = calloc(20001, sizeof(int)); // assuming values in [-10000, 10000]
    fs->size = 0;
    fs->order = 0;
    return fs;
}

void freqStackPush(FreqStack* obj, int val) {
    obj->freq[val + 10000]++;
    obj->elements[obj->size] = val;
    obj->orders[obj->size] = obj->order++;
    obj->size++;
}

int freqStackPop(FreqStack* obj) {
    if (obj->size == 0) return -1;
    
    int maxFreq = 0;
    for (int i = 0; i < obj->size; i++) {
        if (obj->freq[obj->elements[i] + 10000] > maxFreq) {
            maxFreq = obj->freq[obj->elements[i] + 10000];
        }
    }
    
    int bestIdx = -1;
    for (int i = obj->size - 1; i >= 0; i--) {
        if (obj->freq[obj->elements[i] + 10000] == maxFreq) {
            bestIdx = i;
            break;
        }
    }
    
    int val = obj->elements[bestIdx];
    obj->freq[val + 10000]--;
    
    // Remove element at bestIdx
    for (int i = bestIdx; i < obj->size - 1; i++) {
        obj->elements[i] = obj->elements[i + 1];
        obj->orders[i] = obj->orders[i + 1];
    }
    obj->size--;
    
    return val;
}

int main() {
    // Simple implementation for demonstration
    printf("[5,7,5,4]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each pop operation requires scanning all n elements to find maximum frequency

✓ Linear Growth

Space Complexity

O(n)

Storage for all elements and frequency map

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler