Problem Description

You need to design a special stack data structure that supports all standard stack operations plus an additional operation to retrieve the minimum element - all in constant time.

The stack should support these operations:

• MinStack(): Creates a new empty stack
• push(val): Adds a new element val to the top of the stack
• pop(): Removes the top element from the stack
• top(): Returns the value of the top element without removing it
• getMin(): Returns the minimum element currently in the stack

The key challenge is that all operations, including getMin(), must run in O(1) time complexity. This means you cannot simply scan through all elements to find the minimum each time getMin() is called.

The solution uses two stacks:

1. stk1: A regular stack that stores all the elements
2. stk2: An auxiliary stack that keeps track of the minimum element at each state

When pushing a new element:

• Add the element to stk1 normally
• Add to stk2 the minimum between the new element and the current minimum (top of stk2)

When popping an element:

• Remove from both stacks to keep them synchronized

This way, the top of stk2 always contains the minimum element of all elements currently in the stack, allowing getMin() to return it in O(1) time.

The stk2 is initialized with inf (infinity) to handle the edge case when comparing with the first element pushed to the stack.

Intuition

The natural approach to finding the minimum element would be to scan through all elements in the stack, but this takes O(n) time. We need a way to "remember" the minimum element at all times without searching.

The key insight is that when we push elements onto a stack, the minimum element at any point depends on:

1. The new element being pushed
2. The minimum element among all elements below it in the stack

This observation leads us to think: what if we track the minimum element at each level of the stack?

Consider this example:

• Push 5: stack = [5], minimum = 5
• Push 3: stack = [5, 3], minimum = 3
• Push 7: stack = [5, 3, 7], minimum = 3
• Push 2: stack = [5, 3, 7, 2], minimum = 2

Notice that at each level, we need to know what the minimum was up to that point. If we pop 2, the minimum goes back to 3. If we pop 7, the minimum is still 3. If we pop 3, the minimum becomes 5.

This pattern suggests we need to store the "minimum so far" for each element in the stack. We could store pairs (value, min_at_this_point) in a single stack, but using two parallel stacks is cleaner:

• One stack stores the actual values
• Another stack stores the corresponding minimum at each level

When we push a value, we calculate min(new_value, current_minimum) and push this to the minimum stack. This ensures that the top of the minimum stack always holds the current minimum of all elements.

The initialization with inf in stk2 is a clever trick to handle the empty stack case - when the first element is pushed, min(val, inf) will always be val, making it the minimum.

Solution Approach

The implementation uses two stacks to maintain both the elements and their corresponding minimum values:

Data Structures:

• stk1: Main stack to store all the actual elements
• stk2: Auxiliary stack to store the minimum element at each level

Initialization:

def __init__(self):
    self.stk1 = []
    self.stk2 = [inf]

• stk1 starts empty as a regular stack
• stk2 is initialized with inf (infinity) to handle the edge case when comparing with the first pushed element

Push Operation:

def push(self, val: int) -> None:
    self.stk1.append(val)
    self.stk2.append(min(val, self.stk2[-1]))

• Append the value to stk1 normally
• Calculate the new minimum by comparing val with the current minimum (stk2[-1])
• Append this new minimum to stk2
• This ensures stk2[-1] always contains the minimum of all elements in the stack

Pop Operation:

def pop(self) -> None:
    self.stk1.pop()
    self.stk2.pop()

• Remove the top element from both stacks
• This maintains the synchronization between the two stacks
• After popping, stk2[-1] automatically becomes the minimum of the remaining elements

Top Operation:

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

• Simply return the last element of stk1 without removing it

GetMin Operation:

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

• Return the last element of stk2, which is always the current minimum

Time Complexity: All operations run in O(1) time since they only involve appending, removing, or accessing the last element of a list.

Space Complexity: O(n) where n is the number of elements in the stack, as we maintain two stacks of equal size.

Example Walkthrough

Let's walk through a sequence of operations to see how the two-stack approach maintains the minimum element:

Initial State:

• stk1 = []
• stk2 = [inf]

Operation 1: push(4)

• Add 4 to stk1: stk1 = [4]
• Calculate min(4, inf) = 4, add to stk2: stk2 = [inf, 4]
• Current minimum: 4

Operation 2: push(7)

• Add 7 to stk1: stk1 = [4, 7]
• Calculate min(7, 4) = 4, add to stk2: stk2 = [inf, 4, 4]
• Current minimum: 4 (unchanged because 7 > 4)

Operation 3: push(2)

• Add 2 to stk1: stk1 = [4, 7, 2]
• Calculate min(2, 4) = 2, add to stk2: stk2 = [inf, 4, 4, 2]
• Current minimum: 2 (updated because 2 < 4)

Operation 4: getMin()

• Return stk2[-1] = 2
• No changes to stacks

Operation 5: pop()

• Remove from stk1: stk1 = [4, 7]
• Remove from stk2: stk2 = [inf, 4, 4]
• Current minimum automatically reverts to 4

Operation 6: push(1)

• Add 1 to stk1: stk1 = [4, 7, 1]
• Calculate min(1, 4) = 1, add to stk2: stk2 = [inf, 4, 4, 1]
• Current minimum: 1

Operation 7: top()

• Return stk1[-1] = 1
• No changes to stacks

Operation 8: getMin()

• Return stk2[-1] = 1

Notice how stk2 always maintains the minimum at each level, allowing us to retrieve the current minimum in O(1) time by simply accessing the top element.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(): O(1) - Initializing two empty lists (with one having a single element) takes constant time.
• push(val): O(1) - Appending to both stacks and computing the minimum of two values are constant time operations.
• pop(): O(1) - Removing the last element from both stacks is a constant time operation.
• top(): O(1) - Accessing the last element of a list is a constant time operation.
• getMin(): O(1) - Accessing the last element of the second stack is a constant time operation.

Space Complexity:

• O(n) where n is the number of elements in the stack.
• The implementation uses two stacks (stk1 and stk2), each storing up to n elements.
• stk1 stores all the actual values pushed to the stack.
• stk2 stores the minimum value at each state of the stack, maintaining the same size as stk1 (plus the initial inf value).
• Total space used is 2n + 1, which simplifies to O(n).

Common Pitfalls

1. Not Handling Empty Stack Edge Cases

A common mistake is forgetting to handle operations on an empty stack, which can cause runtime errors.

Pitfall Example:

def pop(self) -> None:
    self.stack.pop()  # Raises IndexError if stack is empty
    self.min_stack.pop()

Solution: Add validation checks before performing operations:

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

def top(self) -> int:
    if self.stack:
        return self.stack[-1]
    return None  # or raise an exception

def getMin(self) -> int:
    if len(self.min_stack) > 1:  # Remember min_stack has sentinel value
        return self.min_stack[-1]
    return None  # or raise an exception

2. Forgetting to Initialize min_stack with Sentinel Value

Pitfall Example:

def __init__(self):
    self.stack = []
    self.min_stack = []  # Empty initialization causes error on first push

This causes an IndexError when trying to access self.min_stack[-1] during the first push operation.

Solution: Always initialize min_stack with infinity as a sentinel:

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

3. Using Only One Stack with Tuple Storage

While technically correct, storing tuples like (value, current_min) in a single stack can be less intuitive and harder to debug:

Pitfall Example:

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

Why it's problematic:

• Less readable and maintainable
• Accessing elements requires remembering tuple indices
• More prone to index errors

4. Recalculating Minimum on Every getMin() Call

Pitfall Example:

def getMin(self) -> int:
    return min(self.stack)  # O(n) time complexity!

This defeats the purpose of the problem as it requires O(n) time instead of O(1).

5. Not Synchronizing Both Stacks During Pop

Pitfall Example:

def pop(self) -> None:
    popped_val = self.stack.pop()
    # Forgetting to pop from min_stack or conditionally popping
    if popped_val == self.min_stack[-1]:
        self.min_stack.pop()  # Wrong! Breaks synchronization

This breaks the correspondence between stack positions and their minimums. Always pop from both stacks to maintain synchronization.