Python Program to Implement Min Stack

A Python min stack can be implemented using two lists: one for normal stack operations and one to keep track of minimum values, with methods like push(), pop(), and get_min() to manage elements and retrieve the minimum in constant time.

Examples

Inputpush(3), push(5), get_min(), push(2), push(1), get_min(), pop(), get_min()

Output3, 1, 2

Inputpush(10), push(20), pop(), get_min()

Output10

Inputpush(5), pop(), get_min()

OutputStack is empty

How to Think About It

To implement a min stack, keep two stacks: one normal stack to store all values and another stack to store the minimum values seen so far. When pushing, add the new value to the normal stack and also push it to the min stack if it is smaller or equal to the current minimum. When popping, remove from both stacks if the popped value is the current minimum. This way, the minimum can be retrieved in constant time by looking at the top of the min stack.

Algorithm

1

Create two empty stacks: main stack and min stack.

2

For push operation, add the value to the main stack.

3

If min stack is empty or new value is less than or equal to the top of min stack, push it to min stack.

4

For pop operation, remove the top value from main stack.

5

If the popped value equals the top of min stack, pop from min stack as well.

6

For get_min operation, return the top value of min stack if not empty.

Code

python

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

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

    def pop(self):
        if not self.stack:
            return "Stack is empty"
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val

    def get_min(self):
        if not self.min_stack:
            return "Stack is empty"
        return self.min_stack[-1]

# Example usage
min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
print(min_stack.get_min())  # Output: 3
min_stack.push(2)
min_stack.push(1)
print(min_stack.get_min())  # Output: 1
min_stack.pop()
print(min_stack.get_min())  # Output: 2

Output

3
1
2

Dry Run

Let's trace pushing 3, 5, 2, 1 and popping once, checking minimum after each step.

1

Push 3

stack = [3], min_stack = [3]

2

Push 5

stack = [3, 5], min_stack = [3]

3

Get min

min_stack top = 3

4

Push 2

stack = [3, 5, 2], min_stack = [3, 2]

5

Push 1

stack = [3, 5, 2, 1], min_stack = [3, 2, 1]

6

Get min

min_stack top = 1

7

Pop

pop 1 from stack and min_stack; stack = [3, 5, 2], min_stack = [3, 2]

8

Get min

min_stack top = 2

stack	min_stack
[3]	[3]
[3, 5]	[3]
[3, 5, 2]	[3, 2]
[3, 5, 2, 1]	[3, 2, 1]
[3, 5, 2]	[3, 2]

Why This Works

Step 1: Two stacks keep track

One stack stores all values, the other keeps the minimum values seen so far to quickly find the smallest.

Step 2: Push updates both stacks

When pushing, add the value to the main stack and to the min stack if it is smaller or equal to current minimum.

Step 3: Pop updates both stacks

When popping, remove from min stack only if the popped value is the current minimum to keep min stack accurate.

Step 4: Get minimum in O(1)

The minimum is always the top of the min stack, so it can be returned instantly without searching.

Alternative Approaches

Single stack with tuples

python

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

    def push(self, val):
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self):
        if not self.stack:
            return "Stack is empty"
        return self.stack.pop()[0]

    def get_min(self):
        if not self.stack:
            return "Stack is empty"
        return self.stack[-1][1]

# Example usage
min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
print(min_stack.get_min())  # Output: 3
min_stack.push(2)
min_stack.push(1)
print(min_stack.get_min())  # Output: 1
min_stack.pop()
print(min_stack.get_min())  # Output: 2

Stores each value with current minimum in one stack, saving space but slightly more complex.

Using a linked list

python

class Node:
    def __init__(self, val, curr_min, next=None):
        self.val = val
        self.curr_min = curr_min
        self.next = next

class MinStack:
    def __init__(self):
        self.head = None

    def push(self, val):
        if not self.head:
            self.head = Node(val, val)
        else:
            curr_min = min(val, self.head.curr_min)
            self.head = Node(val, curr_min, self.head)

    def pop(self):
        if not self.head:
            return "Stack is empty"
        val = self.head.val
        self.head = self.head.next
        return val

    def get_min(self):
        if not self.head:
            return "Stack is empty"
        return self.head.curr_min

# Example usage
min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
print(min_stack.get_min())  # Output: 3
min_stack.push(2)
min_stack.push(1)
print(min_stack.get_min())  # Output: 1
min_stack.pop()
print(min_stack.get_min())  # Output: 2

Uses linked list nodes to store values and current minimum, useful if dynamic memory is preferred.

Complexity: O(1) time, O(n) space

Time Complexity

All operations push, pop, and get_min run in constant time because they only access the top of stacks without loops.

Space Complexity

Uses extra space for the min stack which can be up to the size of the main stack in the worst case.

Which Approach is Fastest?

Both two-stack and single-stack-with-tuples approaches have O(1) time but single-stack uses slightly less space and simpler structure.

Approach	Time	Space	Best For
Two stacks	O(1)	O(n)	Clear separation of values and minimums
Single stack with tuples	O(1)	O(n)	Saves space, simpler to manage one stack
Linked list nodes	O(1)	O(n)	Dynamic memory use, no arrays