Min Stack

Patrick Leaton
Published: March 24, 2021, 10:50 p.m.
Problem Description

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

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve 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

 

Constraints:

  • Methods pop, top and getMin operations will always be called on non-empty stacks.

 

Description taken from https://leetcode.com/problems/min-stack/.

Problem Solution

#O(1) Time Operations, O(N) Space
class MinStack:
 
    def __init__(self):
        self.stack = []
       
    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append((x, x))
            return
        stack_min = self.stack[-1][1]
        self.stack.append((x, min(x, stack_min)))
       
    def pop(self) -> None:
        temp = self.stack[-1]
        del self.stack[-1]
        return temp
 
    def top(self) -> int:
        return self.stack[-1][0]
 
    def getMin(self) -> int:
        return self.stack[-1][1]

Problem Explanation

This problem can be solved by having a stack that consists of pair tuples, where the second index of the tuple holds the current minimum.

Let's start by initializing our stack.

    def __init__(self):
        self.stack = []

Next, we will create our push function.

    def push(self, x: int) -> None:

 

In our push function, we will first check if our stack is empty.  

If it is, we will append our input value as the first element, as well as the minimum value then return because there are no other values yet.

        if not self.stack:
            self.stack.append((x, x))
            return

 

If the stack is not empty, we will grab the top value's minimum element for comparison.

        stack_min = self.stack[-1][1]

 

We will then append the input value along with the minimum between the stack's current minimum and our input value.

        self.stack.append((x, min(x, stack_min)))

For our pop function, we can save the top element as a temporary variable, delete the top value, and then return the temporary variable.

    def pop(self) -> None:
        temp = self.stack[-1]
        del self.stack[-1]
        return temp

For our top function, we can return the first element of the (value, min) pair from the top of the stack.

    def top(self) -> int:
        return self.stack[-1][0]

For our getMin function, we can return the second element of the (value, min) pair from the top of the stack.

    def getMin(self) -> int:
        return self.stack[-1][1]