Implement a stack that tracks the minimum value in O(1) time

stackMin.ts

/*
How would you design a stack which in addition to push and pop has a function min which returns
the minimum element. Push pop and min should all operate in O(1) time.
*/


class Node<T> {
  data: T
  next: Node<T>

  public constructor(data: T) {
    this.data = data
  }
}

class MyStack<T> {
  private top: Node<T>

  public pop():Node<T> {
    if (this.top == null) {
      throw "empty stack exception"
    }
    const item = this.top
    this.top = this.top.next
    return item
  }

  public push(item: T): void {
    const t = new Node<T>(item)
    t.next = this.top
    this.top = t
  }

  public peek():Node<T> {
    if (this.top == null) {
      throw "empty stack exception"
    }
    return this.top
  }

  public isEmpty(): boolean {
    return this.top == null
  }
}

class MyMinStack<T> extends MyStack<T> {
  minNode: Node<T>
  minNodeMap = new Map()

  push(num: T) {
    super.push(num)
    const node = super.peek()
  
    this.minNode = addNodeToMap(this.minNodeMap, node, this.minNode)
    if (node.data < this.minNode.data) {
      this.minNode = node
    }
  }

  pop() {
    const node = super.pop()
    const newMinNode = removeNodeFromMap(this.minNodeMap, node, this.minNode)
    this.minNode = newMinNode
    return node
  }
}

interface StackNodeWrapper<T> {
  node: Node<T>
  nextMin: Node<T>
}

function removeNodeFromMap<T>(map: Map<Node<T>, StackNodeWrapper<T>>, node: Node<T>, currentMinNode: Node<T>) {
  if (node !== currentMinNode) {
    return currentMinNode
  }

  const newMin = map.get(node).nextMin
  map.delete(node)
  return newMin
}

function addNodeToMap<T>(map: Map<Node<T>, StackNodeWrapper<T>>, node: Node<T>, currentMinNode: Node<T>) {
  if (currentMinNode && node.data >= currentMinNode.data) {
    return currentMinNode 
  }

  map.set(node, {
    node,
    nextMin: currentMinNode
  })

  return node
}