⚡Flashcard Drill➔
NeetCode #350LC-155MediumStackNC 150NC 250
← Back to All Problems

#350 · #155 · Min Stack(最小栈)

📌 Problem Statement & Constraints

Design a stack supporting push, pop, top and getMin, all in O(1) time. Constraints: -2^31 <= val <= 2^31 - 1; at most 3 * 10^4 calls; pop, top and getMin are only called on a non-empty stack.

💡 Core Algorithmic Approaches

  1. A single stack cannot answer getMin in O(1) because popping the minimum would lose the next minimum.
  2. Keep a parallel stack of running minima: min_stack[i] is the minimum of the first i + 1 elements.
  3. On push, the new minimum is min(val, current_min). On pop, both stacks pop together.
  4. An alternative encodes differences relative to the minimum to save space, but the parallel stack is far clearer.

💻 Benchmark Python3 Implementation

class MinStack:
    def __init__(self):
        self.st = []
        self.mins = []                     # running minimum at each depth

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

    def pop(self) -> None:
        self.mins.pop()                    # keep the two stacks in sync
        self.st.pop()

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

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) for every operation: one push or pop per stack.
💾 Space Complexity
O(n) for the two stacks.

⚠️ Interview Pitfalls & Follow-ups

  • Recomputing min(self.st) in getMin: O(n) per call, defeating the purpose.
  • Storing only the current minimum: after popping it, the previous minimum is lost.
  • Forgetting to keep the two stacks in sync: pop must pop from both.
  • Initialising the minimum stack with a sentinel: using the conditional if self.mins else val handles the empty case without a magic value.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems