[leetcode] Maximum Frequency Stack

problem

code

1st try: Time Limit Exceeded

I don't need to track the sequence of numbers....
just need to track max frequency and frequency of each number

// need to memo sequence
// need to memo frequency

var FreqStack = function() {
    this.top = -1;
    this.stack = [];
    this.freqs = {};
};

/** 
 * @param {number} x
 * @return {void}
 */
FreqStack.prototype.push = function(x) {
    this.stack.push(x);
    this.top++;    
    this.freqs[x] ? this.freqs[x]++ : this.freqs[x] = 1;
    // console.log("--", this);  
};

/**
 * @return {number}
 */
FreqStack.prototype.pop = function() {
    const {key, freq, idx} = this.getMostFreq();
    this.freqs[key]--;
    this.top--;
    const ret = this.stack.splice(idx, 1);
    // console.log(this);
    return ret;
};

FreqStack.prototype.lastIndexOf = function(x) {
    x = typeof x == 'string' ? parseInt(x) : x;
    // console.log("x", x, this.stack, this.stack.lastIndexOf(x));
    return this.stack.lastIndexOf(x);
};

FreqStack.prototype.getMostFreq = function() {
    if (this.top == -1) throw 'Top is -1';
    const keys = Object.keys(this.freqs);
    // console.log(this);
    
    let pop = { key: undefined, idx: -1, freq: -1 };
    for (const key of keys) {
        const freq = this.freqs[key];
        if (pop.freq < freq) {
            pop = { key, freq, idx: this.lastIndexOf(key) };
        } else if (pop.freq == freq) {
            let idx = this.lastIndexOf(key);
            if (pop.idx < idx)
                pop = { key, freq, idx };
        }
    }
    // console.log("pop", pop);
    
    return pop;
};


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

Time: O(N)
Space: O(N)

2nd try

class FreqStack {
  	// key: number, value: frequency
    Map<Integer, Integer> freq;
	// key: maxfreq, value: numbers that hit maxfreq
	// push 5, 1, 5, 5 then { 1:[5, 1], 2:[5], 3:[5] }
    Map<Integer, Stack<Integer>> group;
    int maxfreq;

    public FreqStack() {
        freq = new HashMap();
        group = new HashMap();
        maxfreq = 0;
    }

    public void push(int x) {
      	// find x in the freq map, if not return 0 => f = 0 or freq + 1
        int f = freq.getOrDefault(x, 0) + 1;
      	// reset frequency of x
        freq.put(x, f);
      
      	// check if maxfreq changes
        if (f > maxfreq)
            maxfreq = f;
		// group.get(f) == null then new Stack() return created Stack
      	// so .push(x) possible
        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;
    }
}

Time: O(1)
Space: O(N), ex) [5, 5, 5, 5] or [1, 2, 3, 4, 5]