155. Min Stack

In this tutorial we will solve 155. Min Stack from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 155. Min Stack

Problem statement

In this problem we are asked to create a Stack that supports the following operations push, pop, top, and retrieving the minimum element in constant time.

We are asked to implement the MinStack class.

The MinStack() initializes the stack object.

To push an element val into the stack we use void push(int value).

To remove the top element from the stack we use void pop().

To get the top element of the stack we use int top().

And finally, to get the minimum element in the stack we use int getMin().

Example from leetcode.

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

Constraints:

-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Approach

From the constraints we get to know that the values val will be an integer. So, we will create a stack to save integer values.

The top operation is straight forward. We just have to return the top element of the stack.

We will also maintain a min array which will act like a stack. In this stack we will save the minimum value encountered. Initially, we will set the 0th element of the min array to Infinity.

We will carry out two actions when performing the push operation. Firstly, we will save the value val by pushing it into our stack. And then we will check if val is smaller than or equal to the top element of the min stack. If it is, then we will push this value into the min stack as well.

Similarly, we will carry out two actions when performing the pop operation. Firstly, we will pop an item from the top of the stack. And then we will check if the popped item is equal to the top element in the min stack. If it is, then we will pop the top element from the min stack as well.

For the getMin operation we will simply return the top element from the min stack.

Let us look at the first example.

stack = []
min = [Infinity]

operation: PUSH -2
-> is -2 <= top element of min stack ?
   i.e., -2 <= Infinity ? yes
   so, push -2 into min stack

stack = [-2]
min = [Infinity, -2]


operation: PUSH 0
-> is 0 <= top element of min stack ?
   i.e., 0 <= -2 ? no
   so, we ignore

stack = [-2, 0]
min = [Infinity, -2]


operation: PUSH -3
-> is -3 <= top element of min stack ?
   i.e., -3 <= -2 ? yes
   so, push -3 into min stack

stack = [-2, 0, -3]
min = [Infinity, -2, -3]


operation: GET_MIN
-> return the top element from min stack
   i.e., -3


operation: POP
-> pop top element from the stack
   i.e., -3
-> is -3 === top element of min stack ?
   i.e., -3 === -3 ? yes
   so, pop -3 from min stack

stack = [-2, 0]
min = [Infinity, -2]


operation: TOP
-> return the top element from the stack
   i.e., 0


operation: GET_MIN
-> return the top element from min stack
   i.e., -2

Code

JavaScript

var MinStack = function() {
    this.stack = [];
    this.min = [Infinity];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    if (val <= this.min.at(-1)) this.min.push(val);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const item = this.stack.pop();
    if (item === this.min.at(-1)) this.min.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack.at(-1);
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min.at(-1);
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

TypeScript

class MinStack {
    private stack;
    private mins = [Infinity]

    constructor() {
        this.stack = []
    }

    push(val: number): void {
        this.stack.push(val)
        if (val <= this.mins.at(-1)) {
            this.mins.push(val);
        }
    }

    pop(): void {
        const val = this.stack.pop()
        if (val === this.mins.at(-1)) {
            this.mins.pop();
        }
    }

    top(): number {
        return this.stack.at(-1)
    }

    getMin(): number {
        return this.mins.at(-1);
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Complexity

Time complexity: O(1)

All operations take O(1) time complexity.

Space complexity: O(n)

Since we are saving n items in the stack so space complexity is O(n).