Min Stack

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Build a ADT of min stack that has the following operations all in $O(1)$
  • getMin()
  • pop()
  • push()
  • top()

What is Being Asked?

(One sentence on the actual task.)

• Build getMin() on a stack in $O(1)$

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Constraint -> all functions should be $O(1)$

Trick

• Store min value at each node

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Stack

Time & Space Complexity

• Time: $O(1)$ → Reason: Constant operation
• Space: $O(n)$ → Reason: Storing each element once

Code

class MinStack:
    stack = []
    def __init__(self):
        self.stack = []

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

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

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

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

Common Mistakes / Things I Got Stuck On

• Tried to use Monotonic Stack to solve the problem