Implement a Stack that Supports O(1) Retrieval of the Minimum Element

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

Solution Approach

1. Problem Analysis: The standard push and pop operations of a stack already have O(1) time complexity. However, retrieving the minimum element typically requires traversing the entire stack, resulting in O(n) time. To achieve O(1) retrieval of the minimum, additional space is needed to track the minimum state.

2. Core Idea: Use an auxiliary stack (min stack) to synchronously record the corresponding minimum value for each state of the main stack. The main stack stores the actual data, while the top of the auxiliary stack always holds the minimum value within the current main stack.

3. Operation Details:

   • Initialization: Create two stacks, dataStack (main stack) and minStack (auxiliary stack).
   • Push Operation: Push the element onto the main stack. Simultaneously, compare the new element with the top of the auxiliary stack and push the smaller value onto the auxiliary stack.
   • Pop Operation: Pop the top element from both stacks at the same time.
   • getMin Operation: Directly return the top element of the auxiliary stack.

Implementation Steps

1. Data Structure Definition

   class MinStack:
       def __init__(self):
           self.dataStack = []  # Main stack stores actual data
           self.minStack = []   # Auxiliary stack stores history of minimum values
   

2. Push Operation Implementation

   • Push the new element onto the main stack.
   • If the auxiliary stack is empty, push the new element directly onto it.
   • If the auxiliary stack is not empty, compare the new element with the top of the auxiliary stack and push the smaller value.

   def push(self, val: int) -> None:
       self.dataStack.append(val)
       # If auxiliary stack is empty, or new value is less than or equal to current minimum, push new value
       if not self.minStack or val <= self.minStack[-1]:
           self.minStack.append(val)
       else:
           # Otherwise, push a duplicate of the current minimum
           self.minStack.append(self.minStack[-1])
   

3. Pop Operation Implementation

   • Pop the top element from both stacks simultaneously.
   • Ensures synchronization between the two stacks.

   def pop(self) -> None:
       if self.dataStack:
           self.dataStack.pop()
           self.minStack.pop()
   

4. Retrieving Top and Minimum

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

Optimization
The above implementation may store many duplicate values in the auxiliary stack. Space can be optimized by:

• Having the auxiliary stack only store new minimums, and checking when popping if the minimum is being removed.
• However, this increases code complexity. The basic version already satisfies the O(1) time complexity requirement.

Complexity Analysis

• Time Complexity: All operations are O(1).
• Space Complexity: O(n), requiring extra space for the auxiliary stack.

Key Points Summary

• Maintain synchronous operations between the auxiliary stack and the main stack.
• The top of the auxiliary stack always corresponds to the minimum value in the current state of the main stack.
• Achieve O(1) minimum retrieval by trading space for time.