0155.Min Stack

• Link: 155. Min Stack - Medium
• Track: NeetCode150

Question

Restate the problem

• Design a stack that supports the normal stack operations:
  • push(val)
  • pop()
  • top()
• and also supports:
  • getMin()
• All operations must run in O(1) time.

Edge Case

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	two stack	O(1) per op	$O(n)$

Method 1

The key idea is: for every index, store the minimum value seen so far, so getMin() is always just the top of minstack.

Approach

• Use two stacks:

  • stack stores the actual values
  • minstack stores the minimum value up to each position

• That means:

  • minstack[i] = minimum value among stack[0] to stack[i]

• So when we push(val):

  • if val is smaller than the current minimum, store val
  • otherwise, repeat the previous minimum

• This way, the top of minstack always tells us the minimum value of the current stack.

• When we pop(), we pop from both stacks together.

Complexity

• Time Complexity: O(1) for push, pop, top, and getMin
• Space Complexity: O(n)

Code

class MinStack:
 
    def __init__(self):
        self.stack = []
        self.minstack = [] # min value up to each position
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.minstack and self.minstack[-1] < val:
            self.minstack.append(self.minstack[-1])
        else:
            self.minstack.append(val)
 
    def pop(self) -> None:
        self.stack.pop()
        self.minstack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.minstack[-1]

---

Mistake

• minstack is not really a monotonic stack, min value up to each position