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.

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

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

class FreqStack {
    constructor() {
        this.counts = {}; // frequency of each val pushed
        this.bucket = []; // stack of stacks (bucket[i] is values with frequency i + 1)
        this.maxCount = 0; // max frequency in counts
    }

    push(val) {
        // update counts for val and maxCount
        if (!(val in this.counts)) {
            this.counts[val] = 0;
        }
        this.counts[val]++;
        const count = this.counts[val];
        this.maxCount = Math.max(this.maxCount, count);

        // push val into bucket by its current frequency
        if (!this.bucket[count - 1]) {
            this.bucket.push([]);
        }
        this.bucket[count - 1].push(val);
    }

    pop() {
        // get most recent pushed val with largest frequency
        const val = this.bucket[this.maxCount - 1].pop();
        this.counts[val]--;

        // no value with frequency maxCount
        if (!this.bucket[this.maxCount - 1].length) {
            this.maxCount--;
        }
        return val;
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * var obj = new FreqStack()
 * obj.push(val)
 * var param_2 = obj.pop()
 */

We will use a stack of stacks bucket to store values by both frequency and insertion order. More specifically, bucket[i] is a stack of values with frequency i + 1, where the top of the stack are the more recent elements with said frequency. This means, if we want to get the most frequent value (most recent if there is a tie), our desired value is the top element of the last non-empty stack in bucket. To do so, we keep track of the max frequency maxCount in order to find this stack in bucket (ie. bucket[maxCount - 1]) and pop it. In addition, we also use a hashmap counts to track the frequency of each value in bucket so we know which stack in bucket to push new elements into, as well as when to update maxCount.

Problem​

Solution​

Problem

Solution