Question

Design a stack class that supports the push, pop, top, and getMin operations.

• 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.

Each function should run in O(1)O(1) time.

Example 1

Input : ["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"]

Output : [null,null,null,null,0,null,2,1]

Explanation :

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

Approach

To solve this, we just have to use simple data structure like array and simple coding knowledge.

Initialization

To initialize the min stack, we will use stack to store the values and to get the min value in the stack, we will also use array. But for min value, we will only store min value.

Push

In push, we push all the values in stack, but in min value array we will store only values that are less than or equal to stored value in min array

Algorithm

1. Check if size of stack is 0:

   1. then push the value in min value array

2. If the size is greater than 0 and given value is less than or equal to last value in min array:

   1. then push the given value

3. Push the value in stack.

Pop

When using pop function, not only we have to pop the value from stack but we have to update the min array if the popped value is the last value of min array.

Algorithm

1. Pop the value from stack

2. Check if the popped value in equal to last element in min array:

   1. pop the last value from the min array

Top

In this function, we have to find the last element of stack. We simply return the last value of stack.

getMin

In this function, we have to return the minimum value of stack. To do this, we simply return the last element of min array.

Solution (JS code)

class MinStack {
    constructor() {
        this.stack = [];
        this.minValue = [];
        this.size = 0;
    }

    /**
     * @param {number} val
     * @return {void}
     */
    push(val) {
        if (this.size == 0) {
            this.minValue.push(val);
        }
        else if (this.size > 0 && this.minValue[this.minValue.length-1] >= val) {
            this.minValue.push(val);
        }
        this.stack.push(val);
        this.size++;
    }

    /**
     * @return {void}
     */
    pop() {
        const popValue = this.stack.pop();
        this.size--
        if (popValue === this.minValue[this.minValue.length-1]) {
            this.minValue.pop();
        }
    }

    /**
     * @return {number}
     */
    top() {
        const topIndex = this.size-1;
        return this.stack[topIndex];
    }

    /**
     * @return {number}
     */
    getMin() {
        return this.minValue[this.minValue.length-1]
    }
}

Time Complexity

O(1)

Space Complexity

O(1)