Practice: Min Stack

Problem: https://leetcode.com/problems/min-stack/

Recognition reminder: this is a design problem, not a single function. You build a class that behaves like a stack (push, pop, top) and also answers “what is the smallest value currently in the stack” with getMin, and every one of those four operations must run in O(1). The lesson is that you can carry extra bookkeeping alongside the stack as long as it pushes and pops in lockstep with the data.

Before you start (the five-beat rhythm)

  1. Your Pattern Card for this week is already written.
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided. No hints, no AI, no Discuss tab.
  4. If stuck past the floor, ask the tutor for a hint. Six rungs, one per ask.
  5. Debrief in your commit message before moving to the next problem.

Your target

Fill these in yourself before you look at anyone else’s solution:

Target time complexity per operation:  ____
Target space complexity:               ____

The naive getMin scans the whole stack, which is O(n). The constraint says every operation, including getMin, must be O(1). The interesting question is: what do you have to remember, and when, so that the current minimum is always available without scanning? Whatever you add has to stay correct as values are popped, not just pushed.

The interface you implement

Write a class MinStack in a file named solution.py in this folder (your own work repo, not the course repo). It supports:

MinStack()        # initialize an empty stack
push(val: int)    # push val onto the stack
pop()             # remove the top element (no return value)
top() -> int      # return the top element without removing it
getMin() -> int   # return the current minimum element in the stack

All operations are called only when valid (for example, pop, top, and getMin are not called on an empty stack), exactly as the LeetCode problem guarantees.

Where your code goes

This folder ships only the problem spec and a provided-example test (tests/test_provided.py). Because this is a design problem, the test does not call one function; it drives your MinStack through the operation sequence from the LeetCode example and checks each output. Run it locally before you submit to LeetCode’s judge. The judge is the oracle; the tutor will not confirm your answer by reading it.

Debrief (paste into your commit message) 

1. What pattern did this turn out to be?
2. What was the trigger phrase or input shape that should have made me reach for it?
3. What was the time and space complexity, and what would dominate at scale?
4. What edge case would have broken my first attempt?
5. What would I do differently in three days when I see this cold?