29) Min Stack

time to completion: 5:21, first try! (But with chatGPT and google syntax questions)

class MinStack {
    stack: number[]
 
    constructor() {
        this.stack = []
    }
 
    push(val: number): void {
        this.stack.push(val)
    }
 
    pop(): void {
        this.stack.pop()
    }
 
    top(): number {
        const lastEl = this.stack.length - 1
        return this.stack[lastEl]
    }
 
    getMin(): number {
        return Math.min(...this.stack)
    }
}
 
/**
 * 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()
 */

This was fun to write. I am starting to the like the class-with-method problems. I learned and/or was reminded of a few things from this exercise:

• The spread operator can be used for arguments in a function, specifically Math.min(...someValues)
• There is really no negative indexing in TS like there is in python which is unfortunate

Attempt 2: This was a bit of a mess, but the idea is essentially just this: Instead of finding the min value when your popMin, calculate the min value as you go. But the best way to do this is sort of weird.

Originally, I thought I would just check any inputs from push Math.min() them to replace the this.min of the class as I went. But this doesn’t survive pop(), which may or may not be deleting that value.

So then I changed min to an array, and for getMin always returned the last element. But I found this still didn’t work very well with pop().

ChatGPT had a good approach that wasn’t intuitive to me at all, which was to continually stack the this.min, but just to add to it every pop operation, even when we were keeping min the same. This way, we could rewind the min whenever we wanted, easily.

I still feel like there might be a way to only write data when a new min is found, but it’s certainly more complex to handle this with the pop class when that last min may or may not be the value that’s being popped. So this is what I got:

class MinStack {
    stack: number[]
    min: number[]
 
    constructor() {
        this.stack = []
        this.min = []
    }
 
    getLastMinVal(){
        return this.min[this.min.length-1]
    }
 
    push(val: number): void {
        this.stack.push(val)
        if (this.min.length === 0){
            this.min.push(val)
        } else {
            this.min.push(Math.min(val, this.getLastMinVal()))
        }
    }
 
    pop(): void {
        this.min.pop()
        this.stack.pop()
    }
 
    top(): number {
        const lastEl = this.stack.length - 1
        return this.stack[lastEl]
    }
 
    getMin(): number {
        return this.getLastMinVal()
    }
}
 
/**
 * 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()
 */

It’s more performative at 92ms versus 237ms.

Attempt 3 Bleh, was on a roll and then got a spam call halfway through but otherwise it went well and I tightened things up a bit. Time to completion: 323ms

Code:

class MinStack {
    stack: number[]
    minStack: number[]
 
    constructor() {
        this.stack = []
        this.minStack = []
    }
 
    push(val: number): void {
        this.stack.push(val)
        if (!this.minStack.length){
            this.minStack.push(val)
        } else {
            this.minStack.push(Math.min(val, this.getMin()))
        }
    }
 
    pop(): void {
        this.stack.pop()
        this.minStack.pop()
    }
 
    top(): number {
        return this.stack[this.stack.length-1]
    }
 
    getMin(): number {
        return this.minStack[this.minStack.length-1]
    }
}
 
/**
 * 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()
 */

Overall, I think this particular strategy of compute-as-you-go in this action-log style way of working is new to me, and I think it will be helpful in the future.

Attempt 4 Time to completion: 2:38 All of these attempts are same day. We’ll see how I do after some time passes.