155. Min Stack - Detailed Explanation

Problem Statement

You are asked to design a stack that supports the following operations in constant time:

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

Example Inputs & Outputs:

1. Example 1:

   • Operations:

     push(-2)
     push(0)
     push(-3)
     getMin() -> Returns -3.
     pop()
     top() -> Returns 0.
     getMin() -> Returns -2.
     

   • Explanation:
     After pushing -2, 0, and -3, the minimum element is -3. Once -3 is popped, the new minimum becomes -2.

2. Example 2:

   • Operations:

     push(1)
     push(2)
     getMin() -> Returns 1.
     top() -> Returns 2.
     pop()
     getMin() -> Returns 1.
     

   • Explanation:
     Pushing 1 then 2, the minimum element is 1. Even after popping the top element (2), the minimum remains 1.

3. Example 3:

   • Operations:

     push(3)
     push(4)
     push(2)
     push(1)
     getMin() -> Returns 1.
     pop()
     getMin() -> Returns 2.
     

   • Explanation:
     The stack’s minimum changes as elements are removed. Initially, it’s 1; after popping 1, the new minimum is 2.

Constraints:

• All operations must be executed in constant time, (O(1)).
• It is guaranteed that pop, top, and getMin will always be called on non-empty stacks.

Hints to Approach the Problem

• Hint 1: Consider that if you use a regular stack, a call to getMin() would require scanning the entire stack (which is (O(n))). Think about a way to "remember" the minimum element as you push or pop elements.

• Hint 2: One effective method is to use an auxiliary stack to keep track of the minimum values. Every time you push a new element, you compare it with the current minimum, and update the auxiliary structure accordingly.

Approaches

Approach 1: Brute Force (Not Optimal)

• Idea:
  Use a normal stack for all elements and, for getMin(), iterate over the stack to find the minimum.
• Downside:
  While push, pop, and top would run in constant time, getMin() would run in (O(n)) time, which violates the constant time requirement for all operations.

Approach 2: Two-Stack Method (Optimal)

• Idea:
  Maintain two stacks:

  • Main Stack: Stores all the pushed elements.
  • Min Stack: Stores the current minimum at every push.
    • When you push an element, compare it with the top of the min stack.
      • If the new element is less than or equal to the current minimum, push it onto the min stack.
      • When popping, if the element removed is the same as the top of the min stack, also pop from the min stack.

• How It Works:
  At any moment, the top of the min stack holds the minimum element of the main stack. This guarantees that getMin() is (O(1)).

Approach 3: Single Stack with Pairs

• Idea:
  Instead of maintaining two separate stacks, you can use one stack that stores pairs: (value, current_min).

  • Every time you push a new element, you calculate the new minimum (using the current top of the stack, if any) and push the pair onto the stack.
  • Pop and top operations work as normal; getMin() simply reads the second element of the top pair.

• Trade-off:
  This method uses slightly more space per element but still provides constant time operations.

Python Code