Learning Journal

2/26/2024

Min Stack

class MinStack {
    private arr:number[] = [];
    private curMin:number = Infinity;
    private minVals:number[] = []

    constructor() {}

    push(val: number): void {
        this.arr.push(val);

        if(this.minVals.length === 0 || val <= this.curMin){
            this.minVals.push(val);
            this.curMin = val;
        }
   
    }

    pop(): void {
        const poppedVal = this.arr.pop();
        if(poppedVal === this.curMin) {
            this.minVals.pop();
            this.curMin = this.minVals[this.minVals.length  -1];
        }
    }

    top(): number {
        return this.arr[this.arr.length - 1];
    }

    getMin(): number {
        return this.curMin;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */class MinStack {
    private arr:number[] = [];
    private curMin:number = Infinity;
    private minVals:number[] = []

    constructor() {}

    push(val: number): void {
        this.arr.push(val);

        if(this.minVals.length === 0 || val <= this.curMin){
            this.minVals.push(val);
            this.curMin = val;
        }
   
    }

    pop(): void {
        const poppedVal = this.arr.pop();
        if(poppedVal === this.curMin) {
            this.minVals.pop();
            this.curMin = this.minVals[this.minVals.length  -1];
        }
    }

    top(): number {
        return this.arr[this.arr.length - 1];
    }

    getMin(): number {
        return this.curMin;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

THE PROBLEM

Here is my reasoning when trying to solve this problem. Because all operations of the MinStack class need to be in O(1) time (as per the requirement of the problem), push function needs to push the new element to the end of the array, which means the array hasn't been sorted yet. So, how do we find a min value in unsorted array? We store it somewhere at the time it was pushed to the array so that when getMin is called, we can return it at O(1) time. We can set a private variable to do the job. But the problem is if we pop the min element out, how can we know what is the min value before this min? Well, we need another array to keep track of the min value, and this array will pop whenever the main arr is popped. But, there is still 1 problem: after we push the min value, if we push, for example, 1000 values that are greater than the min value, the 1000 of the same min values will be pushed to the min array unnecessarily. How about we only push the min once, and we only push again when we find another min? We can do that but with a little modify on pop function. We only pop the min array when the min value is popped from the main array.

Revised by ChatGPT

To ensure all operations of the MinStack class are in O(1) time, the push function adds the new element to the end of the array. Since the array is not sorted, we need a way to track the minimum value efficiently. This is achieved by using a private variable curMin to store the current minimum value and an additional array `minVals to keep tracks of the minimum values over time.

When a new value is pushed:

If minVals is empty or the new value is less than or equal to curMin, we update curMin and push the value onto minVals.

When a value is popped:

If the popped value is equal to curMin, we also pop from minVals and update curMin to the new top of minVals.

This approach ensures that getMin can always return the current minimum in O(1) time. To optimize space, we only push onto minVals when a new minimum is encountered, avoiding unnecessary duplicates.