Implement Min Stack

Problem Description
Design a stack that supports standard stack operations (push, pop, top) and also supports retrieving the minimum element in the stack in constant time.

Core Idea
The key challenge is how to quickly (in O(1) time) know which element is the current minimum in the stack after each push and pop operation. If only one stack is used, retrieving the minimum would require traversing all elements each time, resulting in O(n) time complexity. To achieve O(1) time complexity for the getMin operation, we need extra space to record the minimum value at each moment.

Solution: Auxiliary Stack Method
The most classic and intuitive solution is to use an auxiliary stack (min stack) to synchronously record the minimum value for each state of the main stack.

1. Data Structure Design

   • data_stack: The main stack, used to store all pushed elements normally.
   • min_stack: The auxiliary stack (min stack), whose top always records the minimum value among all elements in the current main stack.

2. Detailed Push Operation

   • Step 1: Push the new element x onto the main stack data_stack.
   • Step 2: Handle the min stack min_stack. This is the most crucial step, with two equivalent strategies:
     • Strategy A (Synchronous Push): If the min stack is empty, then x is the current minimum, simply push x onto the min stack. If the min stack is not empty, compare x with the current top element of the min stack, and push the smaller one onto the min stack.
       • min_value = min(x, min_stack[-1])
       • min_stack.push(min_value)
     • Strategy B (Asynchronous, More Space-Efficient): Push x onto the min stack only if the min stack is empty, or if x is less than or equal to the current top element of the min stack. Otherwise, the min stack remains unchanged.
   • Comparison of the Two Strategies:
     • Strategy A has the advantage of very uniform logic; the main stack and min stack always have the same number of elements, making implementation simple. The drawback is that when multiple elements larger than the current minimum are pushed consecutively, the min stack stores many duplicate, identical minimum values, resulting in slightly lower space efficiency.
     • Strategy B has the advantage of higher space efficiency, as the min stack only stores "stage-wise" minimum values. The drawback is that the logic for the pop operation needs to correspond to the push strategy.
   • Example Illustrating Strategy B: Push 3, 4, 2, 1 sequentially.
     • push(3): Main stack [3], min stack empty, push 3 -> [3].
     • push(4): Main stack [3, 4], 4 > 3, min stack unchanged -> [3].
     • push(2): Main stack [3, 4, 2], 2 < 3, push 2 -> [3, 2].
     • push(1): Main stack [3, 4, 2, 1], 1 < 2, push 1 -> [3, 2, 1].

3. Detailed Pop Operation

   • Step 1: Pop the top element from the main stack data_stack, denoted as popped_value.
   • Step 2: Handle the min stack min_stack. The operation here must strictly correspond to the strategy used for the push operation.
     • If Strategy A was used for push: Simply pop the top of the min stack, because the two stacks always have the same height.
     • If Strategy B was used for push: It is necessary to check whether the popped main stack element popped_value is equal to the current top element of the min stack. If they are equal, it means this popped element is a "copy" of the current minimum value, so the top of the min stack also needs to be popped. Otherwise, the min stack remains unchanged.
   • Continuing the Previous Example (Strategy B): Current stack state: Main stack[3,4,2,1], Min stack[3,2,1].
     • pop(): Main stack pops 1. 1 equals the min stack top 1, so min stack also pops 1. Now main stack[3,4,2], min stack[3,2], current minimum is 2.
     • pop(): Main stack pops 2. 2 equals the min stack top 2, so min stack also pops 2. Now main stack[3,4], min stack[3], current minimum is 3.

4. Top Operation

   • Directly return the top element of the main stack data_stack. This operation does not affect the min stack.

5. GetMin Operation

   • Directly return the top element of the auxiliary stack min_stack. Because we carefully maintain the min stack during push and pop operations, its top always represents the current minimum value in the main stack, so the time complexity of this operation is O(1).

Code Implementation (Based on Strategy B, Space-Optimized Version)
The following is an implementation example in Python.

class MinStack:

    def __init__(self):
        # Initialize main stack and min stack
        self.data_stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        # Always push element onto the main stack
        self.data_stack.append(val)
        # Push onto min stack only if min stack is empty, or new value is <= current minimum
        # Note: The "less than or equal to" check handles cases with multiple identical minimum values
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        # Pop element from the main stack
        popped_value = self.data_stack.pop()
        # If the popped element exactly equals the current min stack top (i.e., current minimum), pop min stack too
        if popped_value == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        # Return the top element of the main stack
        return self.data_stack[-1]

    def getMin(self) -> int:
        # Return the top element of the min stack, which is the current minimum
        return self.min_stack[-1]

Complexity Analysis

• Time Complexity: All operations (push, pop, top, getMin) have O(1) time complexity.
• Space Complexity: O(n), where n is the total number of operations. In the worst case (all elements strictly decreasing), the main stack and min stack occupy the same space; on average, the min stack is smaller than the main stack, offering better space efficiency than the dual-stack synchronous Strategy A.