Minimum Stack

Problem Statement

Design a stack class that supports the push, pop, top, and get_min 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 get_min() retrieves the minimum element in the stack.

Each function should run in O(1) time.

Example 1:

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

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

Explanation:
min_stack = MinStack()
min_stack.push(1)
min_stack.push(2)
min_stack.push(0)
min_stack.get_min() # return 0
min_stack.pop()
min_stack.top()    # return 2
min_stack.get_min() # return 1

Constraints:

• -2^{31} <= val <= 2^{31} - 1
• pop, top and get_min will always be called on non-empty stacks.

You should aim for a solution with O(1) time for each function call and O(n) space, where n is the maximum number of elements present in the stack.

Recommended Time and Space Complexity

You should aim for a solution with O(1) time for each function call and O(n) space, where n is the maximum number of elements present in the stack.

Hint 1

A brute force solution would be to always check for the minimum element in the stack for the getMin() function call. This would be an O(n) approach. Can you think of a better way? Maybe O(n) extra space to store some information.

Hint 2

We can use a stack to maintain the elements. But how can we find the minimum element at any given time? Perhaps we should consider a prefix approach.

Hint 3

We use an additional stack to maintain the prefix minimum element. When popping elements from the main stack, we should also pop from this extra stack. However, when pushing onto the extra stack, we should push the minimum of the top element of the extra stack and the current element onto this extra stack.

Solution

Brute Force

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

    def push(self, val: int) -> None:
        self.stack.append(val)

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

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

    def get_min(self) -> int:
        temp_stack = []
        min_val = self.stack[-1]

        while self.stack:
            min_val = min(min_val, self.stack[-1])
            temp_stack.append(self.stack.pop())

        while temp_stack:
            self.stack.append(temp_stack.pop())

        return min_val

Time complexity: O(n) for get_min() and O(1) for other operations. Space complexity: O(n) for get_min() and O(1) for other operations.