LeetCode 155: Minimum Stack

Problem Description

Difficulty: Medium

Design a stack class supporting push, pop, top, and getMin operations.

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.

Each function should run in constant time.

Examples:

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

Constraints:

\(2^{31}\) ≤ val ≤ \(2^{31} - 1\)

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

Initial Solution

This problem differed from the typical LeetCode problems I’d seen before, leaving me unsure on the level of detail needed. Initially, the question seemed redundant considering Python’s list can act as a stack, including a built-in .pop() method. However, the getMin() function is not trivial. My first attempt somehow passed the LeetCode submission (in the bottom 6%), but it was obvious the getMin() function does not meet LeetCode’s requirements. The min(self.stack) needs to iterate through all elements in the list to find the minimum value; thus this function runs in linear time, not constant time, and fails to meet the requirements of problem.

class MinStack:

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

    def push(self, val: int) -> None:
        """Pushes the element val onto the stack."""
        self.stack.append(val)

    def pop(self) -> None:
        """Removes the element on the top of the stack."""
        del self.stack[-1]

    def top(self) -> int:
        """Gets the top element of the stack."""
        return self.stack[-1]

    def getMin(self) -> int:
        """Retrieves the minimum element in the stack."""
        return min(self.stack)

To keep this looking clean, I dispensed with any error handling. It ran fine on LeetCode without any, but in reality the functions should contain things like:

if not self.stack:
            raise IndexError

Also, don’t try to use .remove() instead of del, .pop(), or slicing. The .remove() function looks for a specific value and removes the first occurrence of that value. This will lead to issues when multiple instances of a value are present in the list, as it will remove the first instance rather than the last item, which is the desired behavior for a stack. I learned this when trying to figure out a reasonable alternative to .pop(). Although, it turns out LeetCode doesn’t care if you use .pop() anyway.

Correct Solution

To create a getMin than runs in constant time, we’ll need to trade off some memory by storing the minimum element in another list…

class MinStack:

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = val
        if self.min_stack:
            val = self.min_stack[-1]
        min_val = min(val, min_val)
        self.min_stack.append(min_val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

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

Results

The version above passed LeetCode and beat just over 50% of submissions on time and 99.8% on memory. All functions run in constant time.

NeetCode Solution

Neetcode’s solution is essentially the same. However, the push function uses three lines of code rather than six, so it’s cleaner and avoids some unnecessary variable assignments.

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

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

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