Leetcode 895: Maximum Frequency Stack

CATEGORY: HARD

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

First Example :

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

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 <= 10⁹
At most 2 * 10⁴ 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.

Solution Approach

Solution Logic

In this problem of Maximum Frequency Stack, the main task is to find the frequency of the value in the stack. So, to find the frequency of the value, we use a Map data structure(Map <key, val>) with key as value and Val as the frequency of the number in the stack. We also consider a variable maxfreq to store the highest frequency. Initially, we initialize maxfreq to zero.

If two or more values in the stack have the same (maximum) frequency, then we have to pop the value which is close to the top of the stack. In this case, we can use the Stack data structure to find the top of the stack with maximum frequency. So, we maintain the mapping between frequency and stack. It denotes which element has reached this frequency in an order.

Space Complexity: O(n), where n is the number of elements in the group.

Push(): In the push function we have to add an element to freq and group, we should also update the maxfreq value. Initially, we have to put the given integer x in freq as key and f frequency of number as Val. Integer f is calculated using the getOrDefault function if the key is a new, default value zero is taken otherwise the value will be incremented by one. Later we check whether the maxfreq value is more than the current value of f and update the value. Finally, we push the value to the group. We check whether the stack is associated with f using computeIfAbsent(). If the stack is not present it creates the stack and pushes the value x into the stack.

Time complexity of push() : O(1)

Pop(): In the pop function, we have to remove and return the top most frequent value from Stack. So, we get the most frequent element from the group, pop the element and store it in x. Since we have removed an element we update freq(key, Val) by decrementing the Val of x. Finally, we return the value of x.

Time complexity of pop() : O(1)

Solution Code

class FreqStack {
    public FreqStack() {
       Map<Integer, Integer>  freq = new HashMap();
        Map<Integer, Stack<Integer>> group = new HashMap();
        int maxfreq = 0;
    }


    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        if (f > maxfreq)
            maxfreq = f;


        group.computeIfAbsent(f, z-> new Stack()).push(x);
    }


    public int pop() {
        int x = group.get(maxfreq).pop();
        freq.put(x, freq.get(x) - 1);
        if (group.get(maxfreq).size() == 0)
            maxfreq--;
        return x;
    }
}

class FreqStack {

public FreqStack() {

Map<Integer, Integer> freq = new HashMap();

Map<Integer, Stack<Integer>> group = new HashMap();

int maxfreq = 0;

}

public void push(int x) {

int f = freq.getOrDefault(x, 0) + 1;

freq.put(x, f);

if (f > maxfreq)

maxfreq = f;

group.computeIfAbsent(f, z-> new Stack()).push(x);

}

public int pop() {

int x = group.get(maxfreq).pop();

freq.put(x, freq.get(x) - 1);

if (group.get(maxfreq).size() == 0)

maxfreq--;

return x;

}

Code Logic

This piece of code defines a class called FreqStack that represents a special stack data structure. Let me break it down in simple terms:

Constructor `FreqStack()`:

This is like the blueprint for creating a new FreqStack object. Inside this constructor, the code does the following:

It creates two storage containers: freq (a map to keep track of the frequency of each element) and group (a map that groups elements by their frequency).
It initializes a variable maxfreq to keep track of the maximum frequency of any element.

Method `push(int x)`

This method is used to add an element to the stack. Here’s what it does:

It first checks how many times the element x has been pushed onto the stack and increments its frequency by 1.
It updates the freq map with the new frequency.
If the new frequency is greater than the maximum frequency seen so far, it updates maxfreq to the new frequency.
It puts the element x into a stack in the group map. This stack is associated with the frequency of x.

Method `pop()`:

This method is used to remove and return an element from the stack based on the special rules. Here’s how it works:

It retrieves the element to pop from the stack associated with the maxfreq. This is essentially the element with the highest frequency.
It decrements the frequency of the popped element in the freq map because one occurrence has been removed.
If the stack associated with the maxfreq becomes empty (meaning there are no more elements with that frequency), it reduces the maxfreq by 1.
Finally, it returns the element that was popped from the stack.

In simpler terms, this code maintains a stack of elements and keeps track of their frequencies. When you push an element onto the stack, it records how many times that element has been pushed. When you pop an element, it follows a specific rule to decide which element to pop: the one with the highest frequency. It then updates the frequency and the maximum frequency accordingly.

Leetcode Link for Maximum Frequency Stack – https://leetcode.com/problems/maximum-frequency-stack/

For more Leetcode-explained solutions visit Leetcode Solutions. If you like capture-the-flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page. Happy Leetcoding 🙂

Examples

Solution Approach

Solution Logic

Solution Code

Code Logic

Constructor FreqStack():

Method push(int x)

Method pop():

Leave a Comment Cancel Reply

Constructor `FreqStack()`:

Method `push(int x)`

Method `pop()`: