LeetCode 155: Min Stack Solution in Python Explained

Problem Statement

In LeetCode 155, you’re tasked with implementing a MinStack class:

• MinStack(): Initializes an empty stack.
• void push(int val): Pushes val onto the stack.
• void pop(): Removes the top element.
• int top(): Returns the top element.
• int getMin(): Returns the minimum element in the stack.

All operations must run in O(1) time. This differs from array searching like LeetCode 154: Find Minimum in Rotated Sorted Array II, focusing on stack design rather than search optimization.

Constraints

• -2^31 <= val <= 2^31 - 1
• Methods called on valid stack states (non-empty for pop, top, getMin)
• At most 3 * 10^4 calls

Example

Let’s see a case:

Copy codeInput:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output:
[null,null,null,null,-2,null,0,-2]
Explanation:
<ul>
<li>MinStack(): Empty stack.</li>
<li>push(-2): [-2], min=-2.</li>
<li>push(0): [-2,0], min=-2.</li>
<li>push(-3): [-2,0,-3], min=-3.</li>
<li>getMin(): -3.</li>
<li>pop(): [-2,0], min=-2.</li>
<li>top(): 0.</li>
<li>getMin(): -2.</li>
</ul>

This shows we’re managing a stack with instant minimum access.

Understanding the Problem

How do you solve LeetCode 155: Min Stack in Python? We need a stack supporting O(1) operations, including getMin, despite dynamic changes. For [-2,0,-3], after pushing -2, 0, -3, the minimum becomes -3; popping -3 reverts it to -2. A plain stack can’t track the minimum in O(1)—we need an auxiliary structure. This isn’t a subarray problem like LeetCode 152: Maximum Product Subarray; it’s about stack augmentation. We’ll use: 1. Dual Stack with Minimum Tracking: O(1) time, O(n) space—our best solution. 2. Single Stack with Difference Encoding: O(1) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dual Stack with Minimum Tracking Approach

Explanation

Dual Stack with Minimum Tracking uses two stacks:

• Main Stack: Stores all values.
• Min Stack: Tracks the minimum at each push, pushing the current minimum when a new value is added, popping when a value is removed.

This ensures all operations (push, pop, top, getMin) run in O(1) time, using O(n) space for the min stack. It’s the best solution due to its simplicity, O(1) efficiency, and clear separation of concerns, making it intuitive and robust.

For [-2,0,-3]:

• Push -2: main=[-2], min=[-2].
• Push 0: main=[-2,0], min=[-2,-2].
• Push -3: main=[-2,0,-3], min=[-2,-2,-3].
• Pop: main=[-2,0], min=[-2,-2], getMin=-2.

Step-by-Step Example

Example: ["MinStack","push","push","push","getMin","pop","top","getMin"], [[],[-2],[0],[-3],[],[],[],[]]

Goal: Follow operations, return [null,null,null,null,-2,null,0,-2].

• Step 1: MinStack().
• main_stack = [], min_stack = [].
• Step 2: push(-2).
• main_stack = [-2], min_stack = [-2] (min=-2).
• Step 3: push(0).
• main_stack = [-2,0], min_stack = [-2,-2] (min=-2).
• Step 4: push(-3).
• main_stack = [-2,0,-3], min_stack = [-2,-2,-3] (min=-3).
• Step 5: getMin().
• Return min_stack[-1] = -3.
• Step 6: pop().
• Pop main_stack = [-2,0], min_stack = [-2,-2].
• Step 7: top().
• Return main_stack[-1] = 0.
• Step 8: getMin().
• Return min_stack[-1] = -2.
• Finish: Output matches operations.

How the Code Works (Dual Stack with Minimum Tracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass MinStack:
    def __init__(self):
        # Line 1: Initialize two stacks
        self.main_stack = []
        # Stores all values (e.g., [])
        self.min_stack = []
        # Tracks minimums (e.g., [])

    def push(self, val: int) -> None:
        # Line 2: Push value to main stack
        self.main_stack.append(val)
        # Add to main (e.g., [-2], then [-2,0])

        # Line 3: Update min stack
        if not self.min_stack or val <= self.min_stack[-1]:
            # If empty or val is new min (e.g., -2, then -3 vs -2)
            self.min_stack.append(val)
            # Push val (e.g., [-2], then [-2,-2,-3])
        else:
            # If val > current min (e.g., 0 > -2)
            self.min_stack.append(self.min_stack[-1])
            # Push current min (e.g., [-2,-2])

    def pop(self) -> None:
        # Line 4: Remove top elements
        self.main_stack.pop()
        # Pop from main (e.g., [-2,0,-3]→[-2,0])
        self.min_stack.pop()
        # Pop from min (e.g., [-2,-2,-3]→[-2,-2])

    def top(self) -> int:
        # Line 5: Return top of main stack
        return self.main_stack[-1]
        # e.g., 0 from [-2,0]

    def getMin(self) -> int:
        # Line 6: Return top of min stack
        return self.min_stack[-1]
        # e.g., -2 from [-2,-2]

This detailed breakdown clarifies how the dual stack approach efficiently tracks the minimum.

Alternative: Single Stack with Difference Encoding Approach

Explanation

Single Stack with Difference Encoding uses one stack, storing differences from the current minimum to handle sign changes:

• Push: Encode value relative to current min.
• Pop: Decode to restore previous min.
• Top/GetMin: Extract from encoded top.

It’s a practical alternative, also O(1) time with O(n) space, but more complex due to encoding logic.

For [-2,0,-3]:

• Push -2: [(0,-2)], min=-2.
• Push 0: [(2,-2),(0,-2)], min=-2.
• Push -3: [(3,-3),(2,-2)], min=-3.

Step-by-Step Example (Alternative)

For the same example:

• Push(-2): stack = [(0,-2)], curr_min = -2.
• Push(0): diff = 0-(-2)=2, stack = [(2,-2),(0,-2)], curr_min = -2.
• Push(-3): diff = -3-(-2)=-1<0, update curr_min = -3, stack = [(3,-3),(2,-2)].
• GetMin: -3.
• Pop: Adjust curr_min = -2, stack = [(2,-2)].
• Top: 0.

How the Code Works (Single Stack)

Copy codeclass MinStackSingle:
    def __init__(self):
        self.stack = []
        self.curr_min = float('inf')

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((0, val))
            self.curr_min = val
        else:
            diff = val - self.curr_min
            self.stack.append((diff, self.curr_min))
            if diff < 0:
                self.curr_min = val

    def pop(self) -> None:
        diff, prev_min = self.stack.pop()
        if diff < 0:
            self.curr_min = prev_min

    def top(self) -> int:
        diff, min_val = self.stack[-1]
        return self.curr_min + diff if diff > 0 else self.curr_min

    def getMin(self) -> int:
        return self.curr_min

Complexity

• Dual Stack with Minimum Tracking:
• Time: O(1) – all operations.
• Space: O(n) – two stacks.
• Single Stack with Difference Encoding:
• Time: O(1) – all operations.
• Space: O(n) – one stack.

Efficiency Notes

Dual Stack with Minimum Tracking is the best solution with O(1) time and O(n) space, offering simplicity and clarity—Single Stack with Difference Encoding matches time complexity but uses encoding complexity, saving space conceptually but less intuitive.

Key Insights

• Dual Stack: Direct min tracking.
• Encoding: Compresses min info.
• O(1): Critical for all ops.

Additional Example

For [1,2,3]:

• Goal: Min=1, Top=3.
• Dual: main=[1,2,3], min=[1,1,1].

Edge Cases

• Single Value: [5] → Min=5.
• Negatives: [-1,-2] → Min=-2.
• Duplicates: [1,1] → Min=1.

Both solutions handle these well.

Final Thoughts

LeetCode 155: Min Stack in Python is a foundational stack challenge. The Dual Stack with Minimum Tracking solution excels with its efficiency and simplicity, while Single Stack with Difference Encoding offers a clever space-saving twist. Want more? Try LeetCode 146: LRU Cache for advanced stacks or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 155 on LeetCode with the example above, aiming for the correct sequence—test your skills now!