Implement Min Stack

Problem Overview

The LeetCode problem, popularly known as Min Stack, requires you to design a stack that supports push, pop, top, and retrieving the minimum element in constant time. This problem is an excellent exercise in understanding data structures, especially stacks, and how additional operations can be optimized effectively.

Here's a simplified problem statement:

Design a stack that supports the following operations in constant time:

• push(x): Push element x onto stack.
• pop(): Removes the element on top of the stack.
• top(): Get the top element.
• getMin(): Retrieve the minimum element in the stack.

Understanding the Problem

To solve this problem, we must ensure each operation (push, pop, top, getMin) occurs in constant time, O(1). The challenge lies in maintaining the minimum value in the stack dynamically, as stack operations could change this value frequently.

Considerations:

• Simply using a single stack won't maintain the minimum efficiently since any pop operation could remove the current minimum.
• We need a way to update the minimum value quickly as elements are pushed or popped.

Key DSA Concepts and Theory

Stack

A stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO (Last In First Out). The most recent element added is the first to be removed.

Basic Stack Operations:

• Push: Add an element to the top of the stack.
• Pop: Remove the element from the top of the stack.
• Top: Returns the top element without modifying the stack.

Optimizing with an Auxiliary Stack or Node Structure

To keep track of the minimum element effectively, an auxiliary data structure or modification of the stack node is useful. Common strategies include:

1. Auxiliary Stack: Use another stack that keeps track of minimum values. Every time a new minimum is seen, it's pushed onto this stack.
2. Node Structure with Min Value: Each node can be enhanced to hold its own value and the minimum value of the stack up to that point.

Solution Approach

We will implement the Min Stack using the auxiliary stack approach for simplicity and clarity.

C++ Solution

class MinStack {
private:
    std::stack<int> mainStack;
    std::stack<int> minStack;
    
public:
    MinStack() {
    }
    
    void push(int x) {
        mainStack.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }
    
    void pop() {
        if (mainStack.top() == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
    }
    
    int top() {
        return mainStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
};

Java Solution

class MinStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;

    public MinStack() {
        mainStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        mainStack.pop();
    }

    public int top() {
        return mainStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Explanation

Steps:

1. Push Operation: Push element to the main stack. If it's smaller or equal to the current minimum (top of the min stack), push it onto the min stack.
2. Pop Operation: Pop element from the main stack. If it equals the current minimum, pop it from the min stack as well.
3. Top Operation: Return the top of the main stack.
4. Get Min Operation: Return the top of the min stack.

Time and Space Complexity Analysis

• Time Complexity: Each operation (push, pop, top, getMin) is in constant time, O(1).
• Space Complexity: O(n), where n is the number of elements in the stack. This is due to the additional min stack used to keep track of the minimum elements.

Common Mistakes to Avoid

• Forgetting to update the minStack when popping elements that are the current minimum.
• Not handling empty stacks properly for top() and getMin() operations. It's advised to check if the stack is empty before these operations to prevent runtime errors.

Similar Problems on LeetCode

• LeetCode 155: Min Stack
• LeetCode 716: Max Stack
• LeetCode 232: Implement Queue using Stacks
• LeetCode 225: Implement Stack using Queues

Additional Resources and References

• GeeksforGeeks Stack Data Structure
• Introduction to Algorithm's Chapter on Stacks and Queues
• LeetCode Discuss: Min Stack for additional user insights and alternate solutions.

By understanding and employing these strategies, you can efficiently solve the Min Stack problem, leveraging auxiliary data structures to maintain constant time complexity for all operations.