How to Solve: Min Stack – Complete Guide for FAANG Interviews

How to Solve: Min Stack – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—nail it, and you prove you can design O(1) operations while handling edge cases like a senior engineer."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Min Stack, ensure you understand: 1. Stacks (LIFO) – Push, pop, peek operations in O(1) time. 2. Time/Space Trade-offs – How auxiliary data structures (e.g., extra stacks) impact complexity. 3. Amortized Analysis – Why some operations are O(1) on average (e.g., dynamic arrays).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these exact steps for every Min Stack problem:

1. Clarify Requirements
2. Confirm if getMin() must be O(1) (it always should be).

3. Ask if duplicates are allowed (they usually are).

4. Choose a Data Structure

5. Option 1: Two stacks (main_stack + min_stack).

6. Option 2: Single stack storing (value, current_min) tuples.

7. Initialize

8. If using two stacks, initialize min_stack with infinity (or None).

9. If using tuples, initialize with (value, value) for the first push.

10. Push Operation

11. Two stacks: Push to main_stack. If x <= min_stack[-1], push to min_stack.

12. Tuples: Push (x, min(x, current_min)).

13. Pop Operation

14. Two stacks: Pop from main_stack. If popped value equals min_stack[-1], pop min_stack.

15. Tuples: Pop the tuple; the min is automatically updated.

16. Top Operation

17. Return main_stack[-1] (or the first element of the tuple).

18. GetMin Operation

19. Return min_stack[-1] (or the second element of the tuple).

20. Edge Cases

21. Empty stack (throw error or return None).

22. Duplicate mins (ensure min_stack doesn’t pop prematurely).

23. Time/Space Complexity

24. Time: All operations O(1).

25. Space: O(n) (worst case, all elements are decreasing).

26. Optimize (If Asked)

    • If space is a concern, use tuples to reduce overhead.
    • If asked for O(1) space, explain why it’s impossible (requires O(n) auxiliary space).

? WORKED EXAMPLES

Example 1 – Basic (Two Stacks)

Problem: Design a stack that supports push, pop, top, and getMin in O(1) time.

Thought Process

1. Use two stacks:
2. main_stack for normal operations.
3. min_stack to track the current min.
4. Push: If x <= min_stack[-1], push to min_stack.
5. Pop: If popped value equals min_stack[-1], pop min_stack.
6. getMin: Return min_stack[-1].

Code (Python)

class MinStack:

    def __init__(self):

        self.main_stack = []

        self.min_stack = []


    def push(self, x: int) -> None:

        self.main_stack.append(x)

        if not self.min_stack or x <= self.min_stack[-1]:

            self.min_stack.append(x)


    def pop(self) -> None:

        if not self.main_stack:

            return

        popped = self.main_stack.pop()

        if popped == self.min_stack[-1]:

            self.min_stack.pop()


    def top(self) -> int:

        return self.main_stack[-1]


    def getMin(self) -> int:

        return self.min_stack[-1]

Complexity

• Time: All operations O(1).
• Space: O(n) (worst case, all elements are decreasing).

Why This Works

• min_stack always has the current min at the top.
• We only push to min_stack when x <= current_min, ensuring correctness.

Example 2 – Medium (Single Stack with Tuples)

Problem: Optimize space by using one stack while maintaining O(1) operations.

Thought Process

1. Store (value, current_min) in a single stack.
2. Push: current_min = min(x, stack[-1][1]) if stack is not empty.
3. Pop: Just pop the tuple; the min is automatically updated.
4. getMin: Return stack[-1][1].

Code (Python)

class MinStack:

    def __init__(self):

        self.stack = []


    def push(self, x: int) -> None:

        if not self.stack:

            self.stack.append((x, x))

        else:

            current_min = min(x, self.stack[-1][1])

            self.stack.append((x, current_min))


    def pop(self) -> None:

        if self.stack:

            self.stack.pop()


    def top(self) -> int:

        return self.stack[-1][0]


    def getMin(self) -> int:

        return self.stack[-1][1]

Complexity

• Time: All operations O(1).
• Space: O(n) (same as two stacks, but slightly better constants).

Why This Works

• Each tuple stores the current min at the time of insertion.
• No need for a separate min_stack; the min is always available.

Example 3 – Hard (Follow-up: O(1) Space?)

Problem: Can you design a Min Stack with O(1) space?

Thought Process

1. No, it’s impossible (unless you relax constraints).
2. Why?
3. To track min in O(1), you need O(n) auxiliary space.
4. If you try to store min differences, pop() becomes O(n).
5. Alternative: If the problem allows O(n) time for getMin(), you can scan the stack each time (but this violates the O(1) requirement).

Code (If O(n) getMin is Allowed)

class MinStack:

    def __init__(self):

        self.stack = []


    def push(self, x: int) -> None:

        self.stack.append(x)


    def pop(self) -> None:

        if self.stack:

            self.stack.pop()


    def top(self) -> int:

        return self.stack[-1]


    def getMin(self) -> int:

        return min(self.stack)  # O(n) time!

Complexity

• Time: push, pop, top = O(1). getMin = O(n).
• Space: O(1) (but violates problem constraints).

Why This Works

• Only useful if the interviewer relaxes the O(1) getMin requirement.
• Otherwise, O(1) space is impossible for this problem.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For Min Stack, you’ve got two go-to approaches: 1. Two stacks – main_stack for values, min_stack for mins. Push to min_stack only when x <= current_min. Pop from min_stack only if the popped value equals the current min. 2. Single stack with tuples – Store (value, current_min) in one stack. Saves a little space but same complexity.

Edge cases? Empty stack, duplicates, all decreasing elements. Time complexity? O(1) for all operations. Space? O(n) worst case. And if they ask for O(1) space? Politely explain why it’s impossible—you need O(n) auxiliary space to track mins in O(1) time.

Now go crush that interview. You’ve got this." ?