895. Maximum Frequency Stack

Problem

Tags: Hash Table, Stack, Design, Ordered Set

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^9
• At most 2 * 10^4 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.

Code

C

// 895. Maximum Frequency Stack (12/20/54182)
// Runtime: 421 ms (0.00%) Memory: 67.03 MB (0.00%) 

// Macros and functions in sys/mman.h
#define PROT_READ 0x1
#define PROT_WRITE 0x2
#define MAP_ANONYMOUS 0x20  
#define MAP_PRIVATE 0x02
#define MAP_FAILED ((void *)-1)
extern void* mmap(void* addr, size_t len, int prot, int flags, int fd, off_t offset);
extern int munmap(void* addr, size_t len);

#define SIZE 10000ULL
#define NUMS 1000000001ULL

typedef struct {
    uint16_t most;
    uint16_t counts[NUMS];
    int stacks[SIZE][SIZE];
    uint16_t sizes[SIZE];
} FreqStack;

FreqStack* freqStackCreate() {
    return mmap(NULL, sizeof(FreqStack), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
}

void freqStackPush(FreqStack* this, int val) {
    int count = ++this->counts[val];
    this->stacks[count][++this->sizes[count]] = val;

    if (this->most < this->counts[val]) {
        this->most = this->counts[val];
    }
}

int freqStackPop(FreqStack* this) {
    int val = this->stacks[this->most][this->sizes[this->most]--];

    this->counts[val]--;
    if (this->sizes[this->most] == 0) {
        this->most--;
    }

    return val;
}

void freqStackFree(FreqStack* this) {
    munmap(this, sizeof(FreqStack));
}

/**
 * Your FreqStack struct will be instantiated and called as such:
 * FreqStack* obj = freqStackCreate();
 * freqStackPush(obj, val);
 
 * int param_2 = freqStackPop(obj);
 
 * freqStackFree(obj);
*/

JS

// 895. Maximum Frequency Stack (9/29/54182)
// Runtime: 386 ms (77.94%) Memory: 75.94 MB (55.15%) 

class FreqStack {
    #most = 0;
    #counts = {};
    #stacks = {};
    
    push(val) {
        this.#counts[val] = (this.#counts[val] || 0) + 1;
        this.#most = Math.max(this.#most, this.#counts[val]);
        
        if (!this.#stacks[this.#counts[val]]) {
            this.#stacks[this.#counts[val]] = [];
        }
        this.#stacks[this.#counts[val]].push(val);
    }

    pop() {
        const val = this.#stacks[this.#most].pop();
        
        if (this.#stacks[this.#counts[val]--].length === 0) {
            this.#most--;
        }
        
        return val;
    }
};

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

TS

// 895. Maximum Frequency Stack (9/24/54182)
// Runtime: 303 ms (94.12%) Memory: 72.69 MB (76.47%) 

type frequency = number;

class FreqStack {
    private most: frequency = 0;
    private frequencies: Record<number, frequency> = {};
    private stacks: Record<frequency, number[]> = {};

    public push(val: number): void {
        this.frequencies[val] = (this.frequencies[val] || 0) + 1;
        this.most = Math.max(this.most, this.frequencies[val]);

        if (!this.stacks[this.frequencies[val]]) {
            this.stacks[this.frequencies[val]] = [];
        }
        this.stacks[this.frequencies[val]].push(val);
    }

    public pop(): number {
        const val = this.stacks[this.most].pop();
        if (!this.stacks[this.frequencies[val]--].length) {
            this.most--;
        }
        return val;
    }
}

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