Skip to main content

155 - Min Stack

· 2 min read
Will Holmes

The problem statement​

Design a stack that supports, push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() init's the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Understanding the problem​

The main thing to digest from the problem is that all operations have to be of a constant time execution O(1).

Given that we need to implement a function that is getMin() this tells us that we need to be able to get the minimum value in constant time.

Now doing this by with a reduce or some sort of filter on minimum value comparison would result in getMin() giving us a time complexity of O(n) since we could end up iterating the whole array to get min.

So this tells us we need to be able to store a reference to minimum value upon insertion into our stack.

By doing this it will allow us to fetch the top item from the stack at any point and instantly return the min value. Satisfying our problem.

All the other funcs are pretty simple to implement.

Examples:​

Input

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Explanation

  • MinStack minStack = new MinStack();
  • minStack.push(-2);
  • minStack.push(0);
  • minStack.push(-3);
  • minStack.getMin(); // return -3
  • minStack.pop();
  • minStack.top(); // return 0
  • minStack.getMin(); // return -2

Code solution​

class MinStack {
  private stack: { val: number; min: number }[] = [];

  constructor() {}

  push(val: number): void {
    this.stack.push({
      val,
      min:
        this.stack.length === 0
          ? val
          : Math.min(this.stack[this.stack.length - 1].min, val),
    });
  }

  pop(): void {
    this.stack.pop();
  }

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

  getMin(): number {
    return this.stack[this.stack.length - 1].min;
  }
}

Key Takeaways​

  1. Math.min proves to be a very handy util yet again.
  2. Storing references to values can be a good way to achieve constant time complexity in challenges where you would typically return them in O(n) dealing with arrays / stacks.