LC 151. Min Stack

The problem

First Solution

My stubbornness got the better of me here, and I made the problem more difficult than it was meant to be. The trick is to implement a substack to store the minimum. This way, any previous minimums can kept track of when one is popped from the stack. Of course, you could recalculate the minimum each time, but that would defeat the purpose of the exercise since a stack only allows the top element to be accessed. Technically, this means we wouldn't be able to search the underlying array for a minimum, and doing so would be less performant time-wise.

Where I went mad was to try and do this without any of the array methods or properties because I assumed that it was the easy way out 😂 - classic overthinking! I had also seen someone do it this way in an article or video somewhere so I took the same approach:

class MinStack {
  stack: number[]
  length: number
  minStack: number[]
  minLength: number
  constructor() {
    this.stack = []
    this.length = 0
    this.minStack = []
    this.minLength = 0
  }

  push(val: number): void {
    // Push
    this.stack[this.length] = val
    this.length++

    // Check if new min
    if (val <= this.minStack[this.minLength - 1] || this.minLength === 0) {
      this.minStack[this.minLength] = val
      this.minLength++
    }
  }

  pop(): void {
    if (this.stack[this.length - 1] === this.minStack[this.minLength - 1]) {
      this.minLength--
    }
    this.length--
  }

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

  getMin(): number {
    return this.minStack[this.minLength - 1]
  }
}

Clean up

A more common solution might be one that simply uses the array methods and length property to simplify things. While it isn't much different, here's my cleaner solution:

class MinStack {
  stack: number[]
  min: number[]
  constructor() {
    this.stack = []
    this.min = []
  }

  push(val: number): void {
    // Check if new min and update
    if (val <= this.min.at(-1) || this.min.length === 0) {
      this.min.push(val)
    }
    this.stack.push(val)
  }

  pop(): void {
    // Check if new min and update
    if (this.stack.at(-1) === this.min.at(-1)) {
      this.min.pop()
    }
    this.stack.pop()
  }

  top(): number {
    return this.stack.at(-1)
  }

  getMin(): number {
    return this.min.at(-1)
  }
}