Min Stack

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement MinStack with push, pop, top, and getMin. Every operation must be O(1).

Starter code

class MinStack:
    def __init__(self):
        pass

Test cases

sample

{
  "operations": [
    "MinStack",
    "push",
    "push",
    "getMin",
    "pop",
    "top"
  ],
  "arguments": [
    [],
    [
      -2
    ],
    [
      0
    ],
    [],
    [],
    []
  ]
}

Expected: [null,null,null,-2,null,-2]

Wizard outline

Step 1: Initialize MinStack
Replace the empty starter with the first real state owned by MinStack. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Wizard Stateful Minstack Pop case
Complete the readable core algorithm for one representative Interview case. Synchronizing the stacks restores the prior minimum after the current minimum leaves.
Step 4: Harden the Wizard Stateful Minstack Duplicate Min boundary
Repair the reviewed boundary and pass the complete submission contract. Parallel minimum state avoids reference counting mistakes and keeps every operation O(1).

Footguns and prerequisites

Duplicate minimum values must remain correct after one copy is popped.
python specific rapid fire

Reviewed references

LeetCode 155 — Min Stack

Practice prerequisites

Apply One Stack Reduction(opens in a new tab)
Apply One Stack Reduction isolates the stack is the fully reduced form of the processed prefix and contains no adjacent equal pair. That focused state discipline is required when implementing min stack as a complete Interview Problem.

Recommended approach and implementation

Store one stack for values and one stack for the minimum at each depth.

Why it works: The minimum stack entry at each depth equals the minimum of every value up to that depth.

class MinStack:
    """
    Checkpoint 1: initialize the state owned by this Interview contract.
    Checkpoint 2: assemble the primary transition without hiding the boundary.
    """
    def __init__(self):
        self.values = []
        self.minimums = []
    def push(self, value):
        self.values.append(value)
        self.minimums.append(value if not self.minimums else min(value, self.minimums[-1]))
    def pop(self):
        self.minimums.pop()
        self.values.pop()
    def top(self):
        return self.values[-1]
    def getMin(self):
        return self.minimums[-1]