Min Stack medium

Problem Statement

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.
  • push(val) pushes the element val onto the stack.
  • pop() removes the element on the top of the stack.
  • top() gets the top element of the stack.
  • getMin() retrieves the minimum element in the stack.

Example 1

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

Example 2

Input
["MinStack","push","push","getMin","pop","getMin"]
[[], [2],[0],[],[],[]]

Output
[null,null,null,0,null,2]

Explanation
MinStack minStack = new MinStack();
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.getMin(); // return 2

Steps

  1. Data Structure: We'll use two arrays (or stacks): one to store the actual stack values (stack), and another to store the minimum value encountered so far at each level (minStack).

  2. push(val): When pushing a value:

    • Push the value onto the stack.
    • If minStack is empty or val is less than or equal to the top of minStack, push val onto minStack. This ensures minStack always holds the minimum value at each stack level.

  3. pop(): When popping a value:

    • Pop the value from the stack.
    • If the popped value is equal to the top of minStack, pop from minStack as well. This maintains the consistency of minStack.

  4. top(): Return the top element of the stack.

  5. getMin(): Return the top element of minStack.

Explanation

The key to achieving O(1) time complexity for getMin() is using the auxiliary stack minStack. This stack tracks the minimum value seen at each level of the main stack. By maintaining this parallel stack, we avoid iterating through the main stack to find the minimum each time getMin() is called.

Code

class MinStack {
    stack: number[];
    minStack: number[];

    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val: number): void {
        this.stack.push(val);
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }

    pop(): void {
        if (this.stack.length > 0) {
            const poppedVal = this.stack.pop();
            if (poppedVal === this.minStack[this.minStack.length - 1]) {
                this.minStack.pop();
            }
        }
    }

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

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

Complexity

  • Time Complexity:

    • push(), pop(), top(), getMin(): O(1) All operations involve accessing the top of a stack, which is constant time.

  • Space Complexity: O(N), where N is the number of elements in the stack. We use two stacks, each potentially holding up to N elements.