Skip to main content

Stack

Maximum Frequency Stack

Problem Description

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

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].

Constraints

  • 0 <= val <= 109
  • At most 2 * 104 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.
💡
Try solving it Yourself First !!
This is a design-based problem statement where we need to implement each functionality. We need to understand the flow of execution from the mentioned examples and then implement the logic.

Optimal Approach

Intuition

The focus should be on pop() function because the pop() should return the most frequent elements, if two numbers have the same frequencies, we must return the element that is pushed the latest.

If we observe, to solve this design-based problem, we must have an idea of various data structures and know how to use them efficiently.

Before choosing the data-structure, let's first data structurenote down what are the requirements.

1. We want a data structure that can efficiently track the frequency of each element.
2. We want a data structure where, among the most frequent elements, the number which appears the latest is stored first !!

A data structure to track frequency of each number, can we maintain an array to store frequency of each number ?
Probably not, because if we look at the constraints, the input val ranges from "0 <= val <= 10^9" , can we initialize a vector/list/array of size 10^9 ?
No, it will lead us to a runtime error (Memory Limit Exceeded).

Can we think of a data structure which says that this numbers appeared this many times ?
number x appeared y number of times.
x -> y times.
Is it a map which we can use ??

Yes, we use a map data-structure to store the occurrence of each number.

What is a HashMap/ Map ?

HashMap is a data structure that stores key-value pairs.
If any duplicate Key enters the map, it just updates the value of that particular key to the newly entered value.

The Map data structure exactly aligns with our needs.

Operations we can perform on a map are:-

  1. Insertion
  2. Updation
  3. Search
  4. Removal

We have to remove the latest most frequent element from the data-structure, this means the element which is entered last should be removed first which is also known as Last In First Out.
What is the most intuitive data-structure when we recognise LIFO (Last In First Out) ? It's a Stack !!

We will use a stack, but we must remember that the some or the other way we have to form a connection of the most-frequent element that has occurred latest !!

Alright, if we observe the constraints that, there can be 2*10^4 calls at max. So, a number can have a frequency of 10^4 !!

Here comes a bit of critical thinking, if we want a data-structure where indices can go upto 10^4. Can we treat these indices as frequency of each number?
This means , a linear data-structure if has a size 5. It's indices will be 0,1,2,3,4.
0 can be treated as 0 occurrences, 1 can be treated as single occurrence, 2 can be treated as the number that occurred twice.
In other words, we maintain an list/vector and in each index of the vector, we can keep a stack.

Confused about the declaration of the list with stack data-structure ?

We will create a List containing Stack data structure. The motive behind this is, when we encounter a number we will push the number on-to the stack which is present at index 1.

Let's see how the data-structure looks, after we push these elements,
[5], [7], [5], [7], [4], [5],[5]

When, we call the pop command. We will retrieve

The HashMap will have map= 4 -> 1 , 7 -> 2 , 5 -> 4 .

When, it comes to pop command, we retrieve the last index of the list as it signifies the stack of elements that have appeared the most times. We move to that location which is index 4 in this case in O(1) runtime, retrieve the stack and then pop the top number which signifies that the topmost number has occurred the most times and is pushed the latest.

When, we perform two pop operations, our data-structure looks like this.

When the next pop operation is called, we retrieve the stack at 2nd index of list and delete the top-most number.

We must not forget that the whenever the push and pop operations are called , we update the Map as well.

Let's see how we code it up !!

Approach

Data Structures:
frequencyMap: A hashmap to keep track of the frequency of each element.

  • Key: Element value.
  • Value: Frequency of the element.

stacks: A list of stacks where each stack corresponds to elements of a specific frequency.

  • stacks[i]: Contains elements with frequency i.

Constructor (FreqStack):

  • Initialize frequencyMap as an empty hashmap.
  • Initialize stacks as an empty list of stacks.
  • Add an empty stack to stacks to represent frequency 0 (optional but ensures consistent indexing).

Push Operation (push(x)):

  • Step 1: Retrieve the current frequency of the element x from frequencyMap (default to 0 if not present).
  • Step 2: Increment the frequency of x by 1.
  • Step 3: Update frequencyMap with the new frequency for x.
  • Step 4: Check if a stack exists for the new frequency: If not, add a new empty stack to stacks.
  • Step 5: Add x to the stack corresponding to its new frequency.

Pop Operation (pop()):

  • Step 1: Retrieve the stack corresponding to the highest frequency (last stack in stacks).
  • Step 2: Remove the most recently added element (x) from that stack.
  • Step 3: If the stack becomes empty after removing the element, remove the stack from stacks.
  • Step 4: Decrement the frequency of x in frequencyMap.
  • Step 5: Return the element x.

Dry-Run

Input: ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [3], [3], [1], [2], [1], [3], [], [], [], []]

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

Initial State:

  • fmap: {} (empty hashmap)
  • stacks: [[]] (list with an empty stack at frequency 0)

Step-by-Step Execution:

Operation 1: push(3)

  1. freq = fmap.get(3, 0) + 1 = 1
  2. fmap = {3: 1}
  3. freq == stacks.size() → 1 == 1, so add a new stack to stacks: stacks = [[], [3]]
  4. Add 3 to stacks[1]: stacks = [[], [3]]

Operation 2: push(3)

  1. freq = fmap.get(3, 1) + 1 = 2
  2. fmap = {3: 2}
  3. freq == stacks.size() → 2 == 2, so add a new stack to stacks: stacks = [[], [3], [3]]
  4. Add 3 to stacks[2]: stacks = [[], [3], [3]]

Operation 3: push(1)

  1. freq = fmap.get(1, 0) + 1 = 1
  2. fmap = {3: 2, 1: 1}
  3. freq == stacks.size() → 1 == 3, no new stack needed.
  4. Add 1 to stacks[1]: stacks = [[], [3, 1], [3]]

Operation 4: push(2)

  1. freq = fmap.get(2, 0) + 1 = 1
  2. fmap = {3: 2, 1: 1, 2: 1}
  3. freq == stacks.size() → 1 == 3, no new stack needed.
  4. Add 2 to stacks[1]: stacks = [[], [3, 1, 2], [3]]

Operation 5: push(1)

  1. freq = fmap.get(1, 1) + 1 = 2
  2. fmap = {3: 2, 1: 2, 2: 1}
  3. freq == stacks.size() → 2 == 3, no new stack needed.
  4. Add 1 to stacks[2]: stacks = [[], [3, 1, 2], [3, 1]]

Operation 6: push(3)

  1. freq = fmap.get(3, 2) + 1 = 3
  2. fmap = {3: 3, 1: 2, 2: 1}
  3. freq == stacks.size() → 3 == 3, so add a new stack to stacks: stacks = [[], [3, 1, 2], [3, 1], [3]]
  4. Add 3 to stacks[3]: stacks = [[], [3, 1, 2], [3, 1], [3]]

Operation 7: pop()

  1. topStack = stacks[3]
  2. Pop x = 3 from topStack: stacks = [[], [3, 1, 2], [3, 1], []]
  3. Remove the empty stack from stacks: stacks = [[], [3, 1, 2], [3, 1]]
  4. Update fmap: fmap = {3: 2, 1: 2, 2: 1}
  5. Return 3.

Operation 8: pop()

  1. topStack = stacks[2]
  2. Pop x = 1 from topStack: stacks = [[], [3, 1, 2], [3]]
  3. topStack is not empty, so stacks remains unchanged.
  4. Update fmap: fmap = {3: 2, 1: 1, 2: 1}
  5. Return 1.

Operation 9: pop()

  1. topStack = stacks[2]
  2. Pop x = 3 from topStack: stacks = [[], [3, 1, 2], []]
  3. Remove the empty stack from stacks: stacks = [[], [3, 1, 2]]
  4. Update fmap: fmap = {3: 1, 1: 1, 2: 1}
  5. Return 3.

Operation 10: pop()

  1. topStack = stacks[1]
  2. Pop x = 2 from topStack: stacks = [[], [3, 1]]
  3. topStack is not empty, so stacks remains unchanged.
  4. Update fmap: fmap = {3: 1, 1: 1, 2: 0}
  5. Return 2.

Final Outputs: [null, null, null, null, null, null, null, 3, 1, 3, 2]

Optimal Code in all Languages.
1. C++ Try on Compiler 
class FreqStack {
    // Frequency map to track element frequencies
    unordered_map<int, int> fmap;

    // Vector of stacks where index represents frequency
    vector<stack<int>> stacks;

public:
    FreqStack() {
        // Add a placeholder stack for frequency 0
        stacks.push_back(stack<int>());
    }

    void push(int x) {
        // Calculate the new frequency
        int freq = fmap[x] + 1;

        // Update the frequency map
        fmap[x] = freq;

        // Add a new stack if needed
        if (freq == stacks.size()) stacks.push_back(stack<int>());

        // Add the element to the corresponding frequency stack
        stacks[freq].push(x);
    }

    int pop() {
        // Get the stack corresponding to the highest frequency
        stack<int>& top = stacks.back();

        // Pop the top element
        int x = top.top();
        top.pop();

        // If the stack is empty, remove it
        if (top.empty()) stacks.pop_back();

        // Update the frequency map
        fmap[x]--;

        // Return the popped element
        return x;
    }
};

2. Java Try on Compiler 
class FreqStack {
    // HashMap to track the frequency of each element
    HashMap<Integer, Integer> fmap;

    // List of stacks where each index represents elements with a specific frequency
    List<Stack<Integer>> stack;

    public FreqStack() {
        // Initialize the frequency map
        fmap = new HashMap();

        // Initialize the list of stacks and add a placeholder stack for frequency 0
        stack = new ArrayList();
        stack.add(new Stack());
    }

    public void push(int x) {
        // Calculate the new frequency of the element
        int freq = fmap.getOrDefault(x, 0) + 1;

        // Update the frequency map with the new frequency
        fmap.put(x, freq);

        // If the current frequency exceeds the size of the stack list, add a new stack
        if (freq == stack.size()) stack.add(new Stack());

        // Add the element to the stack corresponding to its frequency
        stack.get(freq).add(x);
    }

    public int pop() {
        // Get the stack corresponding to the highest frequency
        Stack<Integer> top = stack.get(stack.size() - 1);

        // Pop the top element from the stack
        int x = top.pop();

        // If the stack becomes empty, remove it from the list
        if (top.size() == 0) stack.remove(stack.size() - 1);

        // Decrease the frequency of the popped element in the map
        fmap.put(x, fmap.get(x) - 1);

        // Return the popped element
        return x;
    }
}

3. Python Try on Compiler 
class FreqStack:
    def __init__(self):
        # Frequency map to track element frequencies
        self.fmap = {}

        # List of stacks where index represents frequency
        self.stacks = [[]]

    def push(self, x):
        # Calculate the new frequency
        freq = self.fmap.get(x, 0) + 1

        # Update the frequency map
        self.fmap[x] = freq

        # Add a new stack if needed
        if freq == len(self.stacks):
            self.stacks.append([])

        # Add the element to the corresponding frequency stack
        self.stacks[freq].append(x)

    def pop(self):
        # Get the stack corresponding to the highest frequency
        top = self.stacks[-1]

        # Pop the top element
        x = top.pop()

        # If the stack is empty, remove it
        if not top:
            self.stacks.pop()

        # Update the frequency map
        self.fmap[x] -= 1

        # Return the popped element
        return x

4. JavaScript Try on Compiler 
var FreqStack = function() {
    // Frequency map to track element frequencies
    this.fmap = new Map();

    // Array of stacks where index represents frequency
    this.stacks = [[]];
};

FreqStack.prototype.push = function(val) {
    // Calculate the new frequency
    let freq = (this.fmap.get(val) || 0) + 1;

    // Update the frequency map
    this.fmap.set(val, freq);

    // Add a new stack if needed
    if (freq === this.stacks.length) this.stacks.push([]);

    // Add the element to the corresponding frequency stack
    this.stacks[freq].push(val);
};

FreqStack.prototype.pop = function() {
    // Get the stack corresponding to the highest frequency
    let top = this.stacks[this.stacks.length - 1];

    // Pop the top element
    let val = top.pop();

    // If the stack is empty, remove it
    if (top.length === 0) this.stacks.pop();

    // Update the frequency map
    this.fmap.set(val, this.fmap.get(val) - 1);

    // Return the popped element
    return val;
};

Time Complexity: O(1)

Push Operation

  • Frequency Map Update: Updating the frequency of the element in the fmap takes O(1), as it's a map operation.
  • Stack Insertion: Accessing a specific stack based on frequency is an O(1)
    Pushing the element to the stack is an O(1) operation.
  • Overall Time Complexity for Push: O(1)

Pop Operation

  • Get the Highest Frequency Stack: Accessing the last stack in the stack list is O(1).
  • Pop Element from Stack: Removing the top element of the stack is O(1).
  • Frequency Map Update: Decreasing the frequency of the popped element in fmap takes O(1).
  • Remove Empty Stack (if needed): Removing an empty stack from the list is O(1).
  • Overall Time Complexity for Pop: O(1)

Total Time Complexity: Each push and pop operation runs in O(1), making the entire algorithm highly efficient.

Space Complexity: O(n)

Auxiliary Space Complexity
Auxiliary space refers to the temporary or extra space used by the algorithm (excluding input data).

Frequency Map:
For n unique elements, the fmap stores each element with its frequency.
Space required: O(u), where u is the number of unique elements.

List of Stacks:
Each frequency f corresponds to one stack in the stack list.
In the worst case (when all elements are unique and appear only once), there will be n stacks, each holding a single element.
Space required for stacks: O(n).

Auxiliary Space Complexity: O(n+u), where u≤n.

Total Space Complexity
Input Data: The input array size is O(n).
Auxiliary Structures:
Frequency Map: O(u).
List of Stacks: O(n).

Total Space Complexity: O(n+u)
Since u≤n (the number of unique elements cannot exceed the total number of elements), the total space complexity becomes O(n) in the worst case.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems

Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks capacity.

void push(int val) Pushes the given integer val into the leftmost stack with a size less than capacity.

int pop() Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all the stacks are empty.

int popAtStack(int index) Returns the value at the top of the stack with the given index index and removes it from that stack or returns -1 if the stack with that given index is empty.