Implement a Stack with O(1) Time Complexity for Retrieving the Minimum Value

Problem Description
Design a stack data structure that, in addition to supporting standard stack operations (push, pop, top), also supports retrieving the minimum element in the stack in constant time O(1).

Solution Analysis
Standard stack operations push, pop, and top all have O(1) time complexity. However, retrieving the minimum value requires traversing the entire stack, resulting in O(n) time complexity. To achieve O(1) time retrieval of the minimum value, we need to maintain an additional data structure to track minimum value information.

Detailed Solution

Method 1: Auxiliary Stack Approach (Optimal Solution)

Core Idea

• Use two stacks: a main stack (stack) to store all elements normally, and an auxiliary stack (minStack) specifically to store the current minimum value.
• Key point: The top of minStack always corresponds to the current minimum value among all elements in stack.

Implementation Steps

1. Data Structure Initialization

   class MinStack:
       def __init__(self):
           self.stack = []      # Main stack, stores all elements
           self.min_stack = []  # Auxiliary stack, top is always the current minimum
   

2. Push Operation

   • Push the element onto the main stack stack.
   • If min_stack is empty, or the new element ≤ the top element of min_stack, also push the new element onto min_stack.
   • This ensures the top of min_stack is always the current minimum.

   def push(self, val: int) -> None:
       self.stack.append(val)
       # If min_stack is empty, or new value ≤ current minimum, push onto min_stack
       if not self.min_stack or val <= self.min_stack[-1]:
           self.min_stack.append(val)
   

3. Pop Operation

   • Pop the top element from the main stack stack.
   • If the popped element equals the top element of min_stack, it means the current minimum is being removed, so min_stack also needs to pop its top.
   • The top of min_stack will then automatically update to the next smallest value.

   def pop(self) -> None:
       if self.stack:
           val = self.stack.pop()
           # If the popped value is the current minimum, pop from min_stack as well
           if val == self.min_stack[-1]:
               self.min_stack.pop()
   

4. Top Operation

   • Directly return the top element of the main stack stack.

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

5. GetMin Operation

   • Directly return the top element of min_stack, achieving O(1) time complexity.

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

Example Walkthrough

Operation sequence: push(3), push(2), push(1), getMin(), pop(), getMin()

Execution process:
push(3): stack = [3], min_stack = [3]
push(2): stack = [3,2], min_stack = [3,2]  (2<3, push onto min_stack)
push(1): stack = [3,2,1], min_stack = [3,2,1] (1<2, push onto min_stack)
getMin(): return min_stack top 1
pop(): stack = [3,2], pop 1, min_stack also pops 1 → min_stack = [3,2]
getMin(): return min_stack top 2

Edge Case Handling

• Empty stack operations: Check if the stack is empty for pop, top, and getMin operations.
• Duplicate minimum values: Use "≤" comparison to ensure duplicate minima are correctly recorded.

Complexity Analysis

• Time complexity: All operations are O(1).
• Space complexity: O(n), worst-case requiring an extra n space for min_stack.

Method 2: Space-Optimized Approach Storing Differences
For scenarios with stricter space requirements, you can use only one stack by storing the difference between each element and the current minimum. However, this implementation is more complex and less readable. Method 1 is generally the better choice in most situations.