Min Stack (with getMin)

Welcome to a comprehensive guide on the Min Stack! In this lesson, we will create a Min Stack data structure that keeps track of the minimum element in a stack while also maintaining the regular stack operations. Let's dive in!

What is a Min Stack?

A Min Stack is an extension of a regular stack that not only stores elements but also keeps track of the minimum element present in the stack at any given moment. It's useful when dealing with operations that require finding the minimum value.

💡 Pro Tip: Min Stack is particularly helpful in solving problems that require maintaining a sliding window of minimum elements, like finding the minimum number of elements you need to remove to make the stack empty.

Stack and Min Stack Types

Before we start, let's quickly review the types of stacks and Min Stacks:

Regular Stack:
- push(element): Adds an element to the top of the stack.
- pop(): Removes the top element from the stack.
- peek(): Returns the top element without removing it.
- isEmpty(): Checks if the stack is empty.
- size(): Returns the number of elements in the stack.
Min Stack (custom implementation):
- All the above operations, plus:
- getMin(): Returns the minimum element in the stack.

Implementing Min Stack from Scratch

Now, let's implement a custom Min Stack using Python.

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 self.min_stack[-1] >= val:
            self.min_stack.append(val)

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

    def peek(self):
        return self.stack[-1] if self.stack else None

    def getMin(self):
        return self.min_stack[-1] if self.min_stack else None

    def size(self):
        return len(self.stack)

    def isEmpty(self):
        return len(self.stack) == 0

📝 Note: The push() method updates the minimum stack whenever a smaller value is pushed to the regular stack.

Practical Usage

Now that we have our custom Min Stack, let's put it to use in a real-world scenario.

Suppose we want to find the minimum number of elements we need to remove from the stack to make it empty. We can achieve this by repeatedly popping the stack and finding the minimum value until the stack is empty.

python

min_stack = MinStack()

min_stack.push(5)
min_stack.push(3)
min_stack.push(7)
min_stack.push(2)

while min_stack.size() > 0:
    print(f"Minimum: {min_stack.getMin()}")
    min_stack.pop()

🎯 Output:

Minimum: 2
Minimum: 3
Minimum: 2
Minimum: None

As we can see, the script successfully finds the minimum number of elements (2) that need to be removed to make the stack empty.

Quiz Time

Now that you've mastered the Min Stack, you're one step closer to becoming a proficient developer! Keep learning and exploring, and you'll continue to grow your coding skills. Happy coding! 🚀