Design a Min Stack with O(1) Time Complexity

A min stack is a specialized stack data structure that supports retrieving the minimum element in constant time, making it a classic interview problem requiring efficient space-time trade-offs.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected range of operations? (e.g., will there be up to 3*10^4 operations?)
2. Are we allowed to mutate the input stack during operations?
3. Should we return the minimum value or just the minimum value itself?
4. Can we assume all operations will be valid (i.e., no pop on empty stack)?
5. What is the target time complexity for each operation?

Restatement of the problem: Design a stack data structure that supports all standard stack operations (push, pop, top) and additionally can return the minimum element in O(1) time.

Input/Output specification:

• Input: A sequence of operations (push, pop, top, getMin)
• Output: For each getMin operation, return the minimum element in the stack
• All operations must be O(1) time complexity

Constraints:

• All operations (push, pop, top, getMin) must be O(1)
• Stack can contain integers in the range [-2^31, 2^31 - 1]
• Operations are guaranteed to be valid (no pop on empty stack)
• Maximum number of operations is up to 3 * 10^4

Assumptions:

• The stack supports standard LIFO operations
• getMin() should return the minimum element currently in the stack
• We can use additional space for efficiency

Data shape and hidden structure: The problem requires maintaining not just the current state of elements, but also their relative ordering to efficiently compute the minimum. This suggests we need to track minimums in a way that allows O(1) access, potentially requiring auxiliary data structures to store historical minimums or maintain a secondary stack of minimum values.

The key insight is that we can't simply track one global minimum, because when we pop elements, we might have removed the current minimum and need to fall back to a previous minimum value.

2. Pattern Recognition

The problem asks us to design a stack data structure that supports all standard stack operations (push, pop, top) in O(1) time, plus retrieving the minimum element in O(1) time.

Most likely pattern: Dual-stack pattern or Min-heap with stack pattern.

Wording that signals the pattern:

• "All operations must be O(1)" - This indicates we need to precompute or maintain auxiliary information at each operation
• "Get minimum element" - This suggests we're tracking additional state to avoid recomputation on each query
• "Stack operations" - Standard LIFO structure with specific constraints

Why this fits the pattern: The key insight is that we cannot simply track a global minimum, because when we pop elements, we might remove the current minimum and need to know what the next minimum is. This requires maintaining additional information about the state of the stack at each point.

Core insight: We need to maintain the minimum value at each stack level, not just a global minimum. When we push an element, we need to know what the minimum was at that point in the stack's history.

The pattern is about maintaining auxiliary state that allows us to answer queries efficiently without reprocessing the entire data structure. This is a classic example of trading space for time - we use additional storage to avoid expensive recomputation.

This problem is fundamentally about state tracking under LIFO constraints where we must preserve historical minimums in a way that supports efficient retrieval.

3. Approach Evolution

My first instinct is to use a simple stack and keep track of the minimum element with each push/pop operation. But that's O(n²) in worst case because for each element, we might need to scan the entire stack to find the new minimum. Let me think about how to optimize this.

I notice that if I maintain an additional stack or variable to track the minimum, I can reduce it to O(n) time complexity by avoiding redundant scans. The key insight is that we don't need to recalculate the minimum every time - we can keep track of it incrementally.

The core insight is that for a stack, when we push an element, if it's smaller than or equal to the current minimum, we should also record this new minimum. When we pop an element, if it equals our current minimum, we need to update the minimum to the previous one.

Let me think about this more carefully. If I use a second stack to track minimums, each time I push an element that is less than or equal to the current minimum, I also push it to the min stack. When I pop from the main stack, if the popped element equals the top of min stack, I also pop from min stack. This way, min stack always maintains the minimum element at its top.

This approach gives us O(1) time for all operations and O(n) space in worst case, which is optimal for this problem since we need to preserve all elements.

The invariant that must hold is:

1. Main stack contains all elements in LIFO order
2. Min stack contains the minimum element at each state, with proper tracking of when minimums change
3. When we pop from main stack, if popped element equals top of min stack, we must also pop from min stack to maintain correctness

This is a clean and efficient approach that avoids redundant calculations while maintaining all required functionality.

4. Data Structure Choice

For this problem, I need to design a stack that supports push, pop, and getMin operations all in O(1) time.

Primary Data Structures:

1. Main Stack (Integer) - Stores the actual elements in the stack
2. Min Stack (Integer) - Maintains the minimum element at each stack level

Why Each Data Structure Is Needed:

• The main stack is essential for maintaining the actual stack elements and supporting standard push/pop operations
• The min stack is crucial for tracking the minimum value at each stack level, allowing O(1) access to the current minimum without scanning the entire stack

Time and Space Impact:

• Space Complexity: O(n) for both stacks combined - in worst case, each element gets stored in both stacks
• Time Complexity: O(1) for all operations - each operation on either stack is constant time
• Trade-off: Using extra space to achieve optimal time complexity

Helper Structure: No additional helper structures are needed beyond the two stacks. The design maintains a clear one-to-one correspondence between elements in both stacks, where each element in the main stack has its corresponding minimum stored at the same position in the min stack.

This dual-stack approach is optimal because it avoids having to scan the entire stack to find the minimum, which would be O(n) time complexity. The space overhead is acceptable for the significant time complexity improvement.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works.

Example Input: push(5), push(2), push(1), getMin(), pop(), getMin()

Step 1: push(5)

• Main stack: [5]
• Min stack: [5]
• Current min: 5
• Both stacks maintain the invariant that minStack[i] contains the minimum value from bottom to index i

Step 2: push(2)

• Main stack: [5, 2]
• Min stack: [5, 2]
• Current min: 2
• Since 2 ≤ 5, we push 2 to min stack

Step 3: push(1)

• Main stack: [5, 2, 1]
• Min stack: [5, 2, 1]
• Current min: 1
• Since 1 ≤ 2, we push 1 to min stack

Step 4: getMin()

• Return top of min stack: 1
• This gives us the minimum in O(1) time

Step 5: pop()

• Remove from main stack: [5, 2]
• Remove from min stack: [5, 2]
• Current min: 2
• Both stacks are synchronized and maintain their invariants

Step 6: getMin()

• Return top of min stack: 2
• This is the new minimum value

The algorithm correctly maintains the invariant that at any point, the min stack's top always represents the minimum value in the entire stack. The key insight is that we only push to min stack when we're pushing a value ≤ current minimum, ensuring we never lose track of the actual minimum.

The algorithm terminates correctly because:

1. Each push operation maintains stack invariants
2. Each pop operation synchronizes both stacks properly
3. The min stack always reflects the true minimum of elements currently in main stack
4. All operations complete in O(1) time without requiring traversal of entire data structure

6. Java Solution

import java.util.Stack;

public class MinStack {
    private Stack<Integer> stack;      // Main stack to store all elements
    private Stack<Integer> minStack;   // Auxiliary stack to track minimums
    
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        
        // Update minStack with the current minimum
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        if (stack.isEmpty()) return;
        
        int popped = stack.pop();
        
        // If popped element was the minimum, remove it from minStack too
        if (!minStack.isEmpty() && popped == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        if (stack.isEmpty()) return -1; // Or throw exception
        return stack.peek();
    }
    
    public int getMin() {
        if (minStack.isEmpty()) return -1; // Or throw exception
        return minStack.peek();
    }
}

This implementation uses two stacks:

• Main stack stores all elements
• Min stack tracks the minimum element at each state
• When pushing, we maintain the invariant that minStack always contains the current minimum
• When popping, we ensure we only remove from minStack if the popped element was the minimum

The solution handles all required operations in O(1) time with O(n) space complexity, where n is the number of elements.

7. Complexity Analysis

Time Complexity: O(1) for all operations

Each operation (push, pop, top, getMin) runs in constant time:

• Push: O(1) - we perform a constant number of operations on both stacks
• Pop: O(1) - we remove from both stacks in constant time
• Top: O(1) - we access the top element of the main stack in constant time
• GetMin: O(1) - we access the top element of the min stack in constant time

Space Complexity: O(n) in worst case

We use two stacks to store elements:

• Main stack: stores all n elements in the worst case
• Min stack: stores at most n elements (in worst case where elements are in strictly decreasing order)
• Total space: O(n) + O(n) = O(n)

Why these bounds are correct:

The space complexity is O(n) because in the worst case (strictly decreasing sequence), we must store all n elements in both stacks. The min stack will contain n elements when each element is smaller than the previous minimum.

The time complexity is O(1) because we only perform constant-time operations (stack push/pop/access) on both stacks, and never iterate through the entire data structure.

Optimality:

This solution is optimal for the Min Stack problem. Since we need to support getMin() in O(1) time, and the stack operations must remain O(1), we cannot do better than this approach. Any solution that requires more than O(1) time for getMin() would not meet the problem requirements, and any solution that uses less than O(n) space would fail to handle edge cases properly.

8. Edge Cases & Pitfalls

Empty Stack Operations

The most critical edge case is handling operations on an empty stack. When pop(), top(), or getMin() is called on an empty stack, the implementation must handle this gracefully. Our solution assumes that all operations are valid (as per problem constraints), but in practice, you'd want to throw appropriate exceptions or handle these cases explicitly.

Duplicate Minimum Values

A common pitfall is not properly tracking duplicate minimum values. Consider a stack with elements [5, 2, 2, 3]. When we push 2 twice, both instances should be tracked in the min stack to ensure that popping one 2 doesn't incorrectly make the next minimum 3 instead of 2.

Integer Overflow

When dealing with integer values, there's a risk of overflow when tracking minimums. For example, if we're tracking the minimum value and it's Integer.MIN_VALUE, pushing another very small number could cause issues. Our current solution works with standard integers, but in production systems, you might want to consider using long or handling overflow explicitly.

Inconsistent State Management

A key pitfall is maintaining synchronization between the main stack and min stack. If you push to one but not the other, or if you pop from one but not the other, the stack will be in an inconsistent state. Our solution ensures this by always maintaining both stacks in sync.

Memory Management

In a production environment, if you're frequently pushing and popping elements, memory usage can become an issue. The current solution stores every element in both stacks, which could be inefficient for large datasets. However, this is a trade-off between space and time complexity.

Thread Safety

If the MinStack is used in a multi-threaded environment, race conditions could occur. The current implementation is not thread-safe and requires external synchronization if used in concurrent scenarios.

Implementation Mistakes

Common implementation errors include:

1. Not updating the min stack when pushing elements equal to current minimum
2. Forgetting to pop from min stack when popping from main stack
3. Not handling the case where min stack becomes empty after a pop operation
4. Incorrectly assuming that min() returns the top of min stack without proper validation

The solution handles these edge cases by maintaining strict synchronization between both stacks and ensuring that every push/pop operation updates both data structures consistently.

9. Alternative Approaches

There are several alternative approaches to solving the Min Stack problem, each with different trade-offs:

Approach 1: Two Stack Implementation with Value Tracking Instead of storing the actual values in the min stack, we could store the minimum value at each level. When pushing, if the new element is ≤ current minimum, we push it to min stack. When popping, if popped element equals current minimum, we pop from min stack too. This approach requires tracking the current minimum separately and can be more complex to maintain correctness.

Approach 2: Stack of Pairs Use a stack where each element is a pair (value, current_min). This approach stores the minimum at each stack level explicitly. The space complexity increases to O(2n) in worst case, but the logic is more intuitive.

Approach 3: Single Stack with Delta Encoding Store the difference between each element and the current minimum. This can save space but requires careful handling of negative differences and complex recovery logic when elements are popped.

Approach 4: Using Built-in Min/Max Functions Some languages support built-in min/max operations on collections, but this would not satisfy the O(1) requirement for getMin() in a stack implementation.

The chosen solution with two stacks is preferred because it's clean, intuitive, and maintains optimal O(1) time complexity for all operations while using minimal additional space. The two-stack approach is more readable than delta encoding and avoids the complexity of tracking min values explicitly like in approach 1.

The key advantage of our chosen solution is that it's easy to reason about and debug, while still achieving optimal performance characteristics. The alternative approaches either increase space complexity or add unnecessary implementation complexity for the same time bounds.

10. Test Cases

import java.util.*;

public class MinStackTestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic functionality
        MinStack stack = new MinStack();
        stack.push(5);
        stack.push(2);
        stack.push(8);
        System.out.println("Min after pushing 5,2,8: " + stack.getMin()); // Expected: 2
        stack.pop();
        System.out.println("Min after popping: " + stack.getMin()); // Expected: 2
        stack.pop();
        System.out.println("Min after popping: " + stack.getMin()); // Expected: 5
        
        // Test Case 2: Duplicates
        MinStack stack2 = new MinStack();
        stack2.push(3);
        stack2.push(3);
        stack2.push(1);
        System.out.println("Min with duplicates: " + stack2.getMin()); // Expected: 1
        stack2.pop();
        System.out.println("Min after pop: " + stack2.getMin()); // Expected: 3
        
        // Test Case 3: Empty stack operations
        MinStack stack3 = new MinStack();
        try {
            stack3.getMin(); // Should throw exception or handle gracefully
        } catch (Exception e) {
            System.out.println("Empty stack getMin handled properly");
        }
        
        // Test Case 4: Single element
        MinStack stack4 = new MinStack();
        stack4.push(42);
        System.out.println("Single element min: " + stack4.getMin()); // Expected: 42
        stack4.pop();
        System.out.println("After popping single element"); // Should handle gracefully
        
        // Test Case 5: Negative numbers
        MinStack stack5 = new MinStack();
        stack5.push(-1);
        stack5.push(-5);
        stack5.push(0);
        System.out.println("Min with negatives: " + stack5.getMin()); // Expected: -5
        stack5.pop();
        System.out.println("Min after pop: " + stack5.getMin()); // Expected: -5
    }
}

Sample Test Cases:

1. Basic functionality: Push elements 5, 2, 8 and verify min operations work correctly
2. Duplicate values: Push same elements multiple times to test duplicate handling
3. Empty stack: Verify proper handling when min is called on empty stack
4. Single element: Test with only one element in the stack
5. Negative numbers: Ensure min works correctly with negative values

Tricky Test Case:

// Test case with mixed operations and duplicates
MinStack stack = new MinStack();
stack.push(2);
stack.push(1);
stack.push(3);
stack.push(1); // duplicate min
System.out.println(stack.getMin()); // Should return 1
stack.pop(); // Remove last 1
System.out.println(stack.getMin()); // Should still return 1
stack.pop(); // Remove 3
System.out.println(stack.getMin()); // Should return 1

Boundary Test Case:

// Test with maximum integer values
MinStack stack = new MinStack();
stack.push(Integer.MAX_VALUE);
stack.push(Integer.MIN_VALUE);
System.out.println(stack.getMin()); // Should return Integer.MIN_VALUE

11. Final Summary

The core idea is to maintain a stack that can efficiently track the minimum element at any point in O(1) time. This is achieved by using a secondary stack to keep track of the minimum values, ensuring that each operation (push, pop, top, getMin) runs in constant time. The solution works by cleverly maintaining the invariant that the minimum stack always contains the smallest element seen so far, making it both elegant and optimal for the given constraints.

What makes this solution efficient is the use of a separate stack to store minimums, avoiding the need to scan the entire stack on each getMin call. This trade-off of using extra space for constant-time operations is optimal for this problem's requirements, as no better time complexity can be achieved for the getMin operation while maintaining the stack's LIFO property.