Min Stack Design in DSA Python - Build from Scratch

Min Stack Design

📖 Scenario: Imagine you are building a special stack for a game score tracker. This stack not only stores scores but also quickly tells you the lowest score so far. This helps players see their worst performance instantly.

🎯 Goal: You will build a MinStack class that supports push, pop, top, and get_min operations all in constant time.

📋 What You'll Learn

Create a class called MinStack with an __init__ method

Implement a push method that adds an integer to the stack

Implement a pop method that removes the top element

Implement a top method that returns the top element

Implement a get_min method that returns the smallest element in the stack

Use an auxiliary stack to keep track of minimum values

💡 Why This Matters

🌍 Real World

Min stacks are useful in algorithms where you need quick access to the smallest element, such as in stock price tracking or game score analysis.

💼 Career

Understanding how to design efficient data structures like MinStack is important for software engineering roles that require optimization and algorithmic problem solving.

1

Create the MinStack class with initialization

Create a class called MinStack with an __init__ method that initializes two empty lists: stack and min_stack.

DSA Python

class MinStack:
    def __init__(self):
        # Your code here

Hint

Use two lists to store all elements and minimum elements separately.

2

Add the push method

Add a method called push that takes an integer x and appends it to self.stack. Also, append x to self.min_stack if it is empty or if x is less than or equal to the last element in self.min_stack.

DSA Python

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

    def push(self, x):
        # Your code here

Hint

Remember to check if min_stack is empty before comparing.

3

Add pop and top methods

Add a method called pop that removes the last element from self.stack. If the popped element is equal to the last element in self.min_stack, also remove it from self.min_stack. Add a method called top that returns the last element of self.stack.

DSA Python

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

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        # Your code here

    def top(self):
        # Your code here

Hint

Pop from min_stack only if the popped value equals its last element.

Return the last element of stack in top.

4

Add get_min method and print test output

Add a method called get_min that returns the last element of self.min_stack. Then create a MinStack object, push the values 5, 3, 7, pop once, and print the result of get_min().

DSA Python

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

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        if self.stack:
            val = self.stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self):
        if self.stack:
            return self.stack[-1]

    def get_min(self):
        # Your code here

min_stack = MinStack()
min_stack.push(5)
min_stack.push(3)
min_stack.push(7)
min_stack.pop()
print(min_stack.get_min())

Hint

The minimum after popping 7 should be 3.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To store only the minimum elements pushed so far

B. To sort elements in ascending order automatically

C. To retrieve the minimum element in constant time along with stack operations

D. To reverse the order of elements pushed into the stack

Solution

1. Step 1: Understand the Min Stack concept

   A Min Stack is designed to support normal stack operations and also return the minimum element quickly.

2. Step 2: Identify the key feature

   The key feature is retrieving the minimum element in constant time, not sorting or reversing.

3. Final Answer:

   To retrieve the minimum element in constant time along with stack operations -> Option C

4. Quick Check:

   Min Stack = fast minimum retrieval [OK]

Hint: Min Stack always tracks minimum for O(1) retrieval [OK]

Common Mistakes:

• Thinking Min Stack sorts elements
• Assuming it stores only minimum elements
• Confusing with reversing stack order

2. Which of the following is the correct way to initialize a Min Stack class in Python?

easy

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

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

C. class MinStack:
def __init__(self):
self.stack = None
self.min_stack = None

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

Solution

1. Step 1: Check correct attribute initialization

   Attributes must be initialized with self to be instance variables.

2. Step 2: Verify list initialization

   Both stack and min_stack should be empty lists initialized with self.

3. Final Answer:

   class MinStack:\n def __init__(self):\n self.stack = []\n self.min_stack = [] -> Option D

4. Quick Check:

   Use self for instance variables [OK]

Hint: Always use self to define instance variables in __init__ [OK]

Common Mistakes:

• Not using self for attributes
• Initializing attributes as None instead of lists
• Assigning self to a list directly

3. What will be the output of the following code snippet?

min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
min_stack.push(2)
min_stack.push(1)
min_stack.pop()
print(min_stack.get_min())

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push operations and min tracking

   Push 3 (min=3), push 5 (min=3), push 2 (min=2), push 1 (min=1).

2. Step 2: Pop removes 1, min updates to 2

   After popping 1, the minimum is the next smallest, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pop removes min 1, next min = 2 [OK]

Hint: Pop min, next min is previous min in min stack [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing push order with min updates
• Ignoring min stack updates on pop

4. Identify the bug in this Min Stack pop method and choose the correct fix:

def pop(self):
    if self.stack:
        self.stack.pop()
        self.min_stack.pop()

medium

A. No bug; code is correct

B. Pop from min_stack only if popped element equals current min

C. Pop from min_stack before popping from stack

D. Check if min_stack is empty before popping it

Solution

1. Step 1: Understand pop logic in Min Stack

   Pop from min_stack only if the popped element is the current minimum to keep min_stack accurate.

2. Step 2: Identify bug and fix

   Current code always pops min_stack, which can cause errors if min_stack is out of sync.

3. Final Answer:

   Pop from min_stack only if popped element equals current min -> Option B

4. Quick Check:

   Pop min_stack conditionally to keep min correct [OK]

Hint: Pop min_stack only if popped value equals current min [OK]

Common Mistakes:

• Always popping min_stack without condition
• Not checking min_stack emptiness
• Changing pop order incorrectly

5. You want to design a Min Stack that supports push, pop, top, and get_min all in O(1) time. Which approach is best?

hard

A. Use two stacks: one for all elements, one for current minimums

B. Use a queue to store elements and a variable for min

C. Use one stack and scan all elements to find min on get_min

D. Use a linked list and traverse to find min on each get_min

Solution

1. Step 1: Analyze time complexity requirements

   All operations must be O(1), so scanning or traversing is not allowed.

2. Step 2: Choose data structure approach

   Using two stacks, one for elements and one for minimums, allows constant time min retrieval.

3. Final Answer:

   Use two stacks: one for all elements, one for current minimums -> Option A

4. Quick Check:

   Two stacks = O(1) min retrieval [OK]

Hint: Two stacks track elements and minimums for O(1) min [OK]

Common Mistakes:

• Using scanning which is O(n)
• Using queue which doesn't support stack operations
• Using linked list traversal for min