Min Stack - Java Solution

1. Introduction

This post covers the implementation of a special data structure - Min Stack. The Min Stack is designed to operate like a regular stack but with an added feature of retrieving the minimum element in constant time. This functionality is particularly useful in scenarios where efficient access to the minimum element is critical.

Problem

The task is to design a stack that supports push, pop, top, and retrieving the minimum element in constant time. The class MinStack must be implemented with methods for each of these operations, ensuring that each function operates with O(1) time complexity.

2. Solution Steps

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

2. push(int val): Push the value onto the main stack. If the minStack is empty or the value is less than or equal to the current minimum, also push it onto the minStack.

3. pop(): Pop the top element from the main stack. If the popped element is the same as the top of the minStack, also pop from the minStack.

4. top(): Return the top element of the main stack.

5. getMin(): Return the top element of the minStack, which is the current minimum in the stack.

3. Code Program

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

    // Initialize the MinStack object
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    // Push element onto the stack
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    // Remove the element on top of the stack
    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    // Get the top element of the stack
    public int top() {
        return stack.peek();
    }

    // Retrieve the minimum element in the stack
    public int getMin() {
        return minStack.peek();
    }
}

public class Main {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("Minimum: " + minStack.getMin()); // -3
        minStack.pop();
        System.out.println("Top: " + minStack.top());       // 0
        System.out.println("Minimum: " + minStack.getMin()); // -2
    }
}

Output:

Minimum: -3
Top: 0
Minimum: -2

Explanation:

1. MinStack: The MinStack class uses two stacks: stack for regular stack operations and minStack to keep track of the minimum element.

2. push: When a new element is pushed, it is always added to the stack. If it's smaller than the current minimum, it is also pushed onto minStack.

3. pop: Pops the top element from stack. If this element is the current minimum, it is also popped from minStack.

4. top: Simply returns the top element of stack.

5. getMin: Returns the top element of minStack, which is the current minimum in stack.

6. This design ensures that all operations - push, pop, top, and getMin are performed in O(1) time complexity.

7. The Main class demonstrates the usage of MinStack with a sequence of operations, showcasing how the minimum element is tracked efficiently.