Min Stack - Python Solution

1. Introduction

The "Min Stack" problem is a design challenge that involves creating a stack data structure capable of returning the minimum element in constant time. This problem is a test of understanding advanced data structure concepts and implementing them in an efficient manner.

Problem

Design a stack, named MinStack, that supports push, pop, top, and retrieving the minimum element operations. All operations should have O(1) time complexity. The class should support:

- MinStack(): Initializes the stack object.

- void push(int val): Pushes the element val onto the stack.

- void pop(): Removes the element on the top of the stack.

- int top(): Gets the top element of the stack.

- int getMin(): Retrieves the minimum element in the stack.

2. Solution Steps

1. Use two stacks: one to store all the elements (stack) and another to store the minimum elements (minStack).

2. For each push operation, add the value to stack and update minStack with the current minimum.

3. For each pop operation, pop from both stack and minStack.

4. The top operation returns the top element of stack.

5. The getMin operation returns the top element of minStack, which is the current minimum.

6. Ensure that all operations maintain O(1) time complexity.

3. Code Program

class MinStack:

    def __init__(self):
        self.stack = []
        self.minStack = []

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

    def pop(self):
        self.stack.pop()
        self.minStack.pop()

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

    def getMin(self):
        return self.minStack[-1]

# Example Usage
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin()) # Output: -3
minStack.pop()
print(minStack.top())   # Output: 0
print(minStack.getMin()) # Output: -2

Output:

-3
0
-2

Explanation:

1. Dual Stack Approach: Uses two stacks to maintain the elements and the current minimums.

2. Push Operation: Adds elements to both stacks, updating the minimum stack with the smallest value.

3. Pop Operation: Removes the top element from both stacks, ensuring the minimum stack remains accurate.

4. Top Operation: Returns the top element from the main stack.

5. GetMin Operation: Returns the current minimum from the minimum stack.

6. Constant Time Complexity: All operations are designed to run in O(1) time.

7. Practical Implementation: Demonstrates how to design a data structure with specific time complexity requirements.