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.