Coding Interview Questions | Min Stack

January 18th, 2024

Min Stack Problem Introduction:

This summary will talk about my solution to the min stack problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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

Implement the MinStack class:

MinStack() initializes 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.

How do you solve the Min Stack Problem?

Solution:

class MinStack {
  private stack: number[];
  private currentMin: number;
  constructor() {
    this.stack = [];
    this.currentMin = Infinity;
  }

  push(val: number): void {
    if (val < this.currentMin) {
      this.currentMin = val;
    }
    this.stack.push(val);
  }

  pop(): void {
    if (!this.stack.length) {
      return;
    }
    const poppedElement = this.stack.pop();

    if (poppedElement === this.currentMin) {
      let newMin = Infinity;

      for (const element of this.stack) {
        if (element < newMin) {
          newMin = element;
        }
      }

      this.currentMin = newMin;
    }
  }

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

    return 0;
  }

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

MinStack Solution Summary:

Below is a breakdown of the key aspects of the solution above for the MinStack problem:

1. Stack Implementation: The MinStack class utilizes a private array stack to implement the stack data structure. It keeps track of elements pushed onto the stack.

2. Minimum Element Tracking: The class also maintains a private variable currentMin to keep track of the minimum element in the stack. This is updated whenever a new element is pushed onto the stack.

3. Push Operation: The push method adds elements to the stack. It also updates the currentMin if the newly pushed element is smaller than the current minimum.

4. Pop Operation: The pop method removes the top element from the stack. If the popped element is the current minimum, it iterates through the remaining elements in the stack to find the new minimum. While we do iterate through the current stack array if the popped element is the current minimum in the stack, the cost of this iteration is amortized over the length of the array, meaning these iterations should be minimal as compared to the number of pop operations performed on the stack in general. This ensures the amortized time complexity of this function is O(1).

5. Top Operation: The top method retrieves the top element of the stack if the stack is non-empty.

6. Get Minimum Operation: The getMin method retrieves the current minimum element in the stack.

Complexities

1. Time Complexity:

   • Push, Pop, Top, GetMin: All operations have an O(1) time complexity, where the amortized time complexity of the pop operation is described above.

2. Space Complexity:

   • Stack Storage: The space complexity is O(n), where n is the number of elements pushed onto the stack.
   • Additional Storage: The class maintains additional storage for currentMin. This is however a constant, meaning the overall storage complexity of the class is dominated by the space complexity of the stack variable itself.