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

Example 1:

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

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, so 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 which is popped.

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;

}

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 🙂

Leetcode 895: Maximum Frequency Stack

Examples

Solution Approach

Solution Code

2 thoughts on “Leetcode 895: Maximum Frequency Stack”

Leave a Comment Cancel Reply