Java Coding Challenge - Stack Min Problem

Introduction

The Stack Min Problem requires implementing a stack that supports the following operations efficiently:

• push(x): Push an element onto the stack.
• pop(): Remove the element from the top of the stack.
• getMin(): Retrieve the minimum element in the stack in constant time O(1).

The challenge is to maintain the minimum value efficiently, even as elements are added or removed from the stack.

Approach

Using Two Stacks

To efficiently solve the Stack Min Problem, we can use two stacks:

1. Main Stack: Stores all the elements of the stack as usual.
2. Min Stack: Keeps track of the minimum elements. Each time we push a value onto the main stack, we also push the current minimum onto the min stack.

Why Two Stacks?

• Main Stack: Handles all the normal stack operations (push, pop, peek).
• Min Stack: Only keeps track of the minimum value at each state of the stack. By comparing the new value with the current minimum, we ensure that the minimum is always available at the top of the min stack. This allows O(1) access to the minimum value.

Java Code Implementation

MinStack Class

import java.util.Stack;

public class MinStack {
    private Stack<Integer> mainStack; // Main stack to store all elements
    private Stack<Integer> minStack;  // Min stack to store minimum elements

    // Constructor to initialize the stacks
    public MinStack() {
        mainStack = new Stack<>();
        minStack = new Stack<>();
    }

    // Push element onto the stack
    public void push(int value) {
        mainStack.push(value); // Push to main stack

        // Push to min stack: only push if the stack is empty or the current value is <= minStack top
        if (minStack.isEmpty() || value <= minStack.peek()) {
            minStack.push(value);
        }
    }

    // Pop element from the stack
    public int pop() {
        if (mainStack.isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }

        int poppedValue = mainStack.pop();

        // If the popped value is the same as the minStack top, pop the minStack as well
        if (!minStack.isEmpty() && poppedValue == minStack.peek()) {
            minStack.pop();
        }

        return poppedValue;
    }

    // Get the minimum element in the stack
    public int getMin() {
        if (minStack.isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }

        return minStack.peek(); // The top of the minStack is the minimum element
    }
}

Explanation

1. push(x):

   • Push the value onto the mainStack as usual.
   • If minStack is empty or the value is smaller than or equal to the top of minStack, push it onto minStack.

2. pop():

   • Pop the top element from mainStack.
   • If the popped value matches the top element of minStack, pop minStack as well (to maintain the correct minimum).

3. getMin():

   • Return the top element of minStack, which is always the minimum element in the stack.

Main Class to Test the MinStack

public class Main {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();

        // Push elements
        minStack.push(5);
        minStack.push(2);
        minStack.push(3);
        System.out.println("Minimum: " + minStack.getMin()); // Output: 2

        // Pop and check minimum
        minStack.pop();
        System.out.println("Minimum after pop: " + minStack.getMin()); // Output: 2

        // Push more elements and check minimum
        minStack.push(1);
        System.out.println("Minimum after pushing 1: " + minStack.getMin()); // Output: 1

        // Pop again and check minimum
        minStack.pop();
        System.out.println("Minimum after popping 1: " + minStack.getMin()); // Output: 2
    }
}

Example Output:

Minimum: 2
Minimum after pop: 2
Minimum after pushing 1: 1
Minimum after popping 1: 2

Time Complexity

• Push: O(1)
• Pop: O(1)
• GetMin: O(1)

All operations are performed in constant time, including retrieving the minimum element.

Space Complexity

• Space Complexity: O(n), where n is the number of elements in the stack. The worst-case scenario is that every element is smaller than the previous one, meaning both mainStack and minStack contain all elements.

Conclusion

In this solution, we used two stacks to efficiently maintain the minimum element while performing stack operations in constant time. The approach ensures that we can always retrieve the minimum element in O(1) time, even as the stack grows and shrinks. This is a common interview question that tests both understanding of stack operations and how to optimize auxiliary operations like getMin().