Introduction

The Min Stack problem involves designing a stack that supports retrieving the minimum element efficiently.

The stack should support:

push(x)pop()
top()
getMin()

Rules:

  • all operations should work efficiently
  • minimum element retrieval should be fast

The task is to:

  • design a stack supporting
    constant-time minimum lookup

This problem is one of the most important applications of:

 Stack Data Structure

This problem helps in understanding:

  • stack design
  • auxiliary stacks
  • constant-time retrieval
  • data structure optimization

Example

Operations:push(5)
push(2)
push(7)
getMin()

Output:
2

Explanation:
Stack:
[5,2,7]

Minimum element:
2

Constraints

-2^31 <= val <= 2^31 - 1
Operations:
push, pop, top, getMin will always be valid

Approach 1 : Brute Force Traversal

Explanation

The simplest way is:

  1. Use normal stack
  2. Traverse stack whenever:
    • getMin() is called

This works but minimum retrieval becomes slow.

Steps

  1. Push elements normally.
  2. Pop elements normally.
  3. Traverse stack for minimum.
  4. Return smallest element.

Dry Run

Push:5
2
7

Stack:
[5,2,7]

Traverse stack:
Minimum = 2

Result:
2

Brute Force Code

Complexity Analysis

Time Complexity:push()  -> O(1)pop()   -> O(1)
top()   -> O(1)
getMin()-> O(n)
Explanation:
Minimum requires traversal.

Space Complexity: O(n)
Explanation:
Stack stores elements.

Approach 2 : Two Stack Optimization

Explanation

The optimized solution uses:

 Two Stacks

Idea:

  • one stack stores elements
  • another stack stores:
    • minimum values

Whenever new minimum appears:

  • push into min stack

This allows:

 O(1)

minimum retrieval.

Steps

  1. Create normal stack.
  2. Create min stack.
  3. Push minimum values separately.
  4. Remove from min stack when needed.
  5. Return top of min stack for minimum.

Dry Run

Push 5
Main Stack:
[5]

Min Stack:
[5]

Push 2

Main Stack:
[5,2]

Min Stack:
[5,2]

Push 7

Main Stack:
[5,2,7]

Min Stack:
[5,2]

getMin():
2

Two Stack Code

Complexity Analysis

Time Complexity:
push()   -> O(1)
pop()    -> O(1)
top()    -> O(1)
getMin() -> O(1)
Explanation:
All operations use stack top access.
Space Complexity: O(n)
Explanation:
Additional min stack is used.

Edge Cases

  1. Duplicate minimum values
  2. Single element stack
  3. Negative numbers
  4. Large values
  5. Pop minimum element

Why This Problem is Important

Min Stack helps in understanding:

  1. Stack optimization
  2. Auxiliary data structures
  3. Constant-time operations
  4. Data structure design
  5. Efficient retrieval systems

It is one of the most important stack design interview problems.

Real-World Applications

Min tracking concepts are used in:

  1. Financial systems
  2. Monitoring systems
  3. Database optimization
  4. Real-time analytics
  5. Sliding window processing

Common Mistakes

  1. Forgetting duplicate minimum handling
  2. Incorrect min stack removal
  3. Empty stack access
  4. Wrong minimum updates

Interview Tips

Interviewers often expect:

  1. O(1) minimum retrieval
  2. Auxiliary stack explanation
  3. Data structure optimization reasoning

Always explain:

  • why second stack is needed
  • how minimum values are tracked
  • why operations remain constant time

Related Questions

  1. Valid Parentheses
  2. Implement Stack using Queue
  3. Next Greater Element I
  4. Largest Rectangle in Histogram
  5. Daily Temperatures

Final Takeaway

The Min Stack problem is a fundamental stack design problem that teaches auxiliary stack optimization and constant-time minimum retrieval techniques. Understanding this problem builds a strong foundation for advanced stack and data structure design interview problems.