The easy way

  • Creating a min stack is easy if you don’t have to do all the operations in constant time
  • stack.push(val)
    • `minVal = min(minVal, val)
    • Push to stack
    • Time complexity: O(1)
  • stack.min()
    • return minVal
    • Time complexity: O(1)
  • stack.top()
    • Same as a normal stack
    • Time complexity: O(1)
  • stack.pop()
    • If stack.top() == stack.min()
      • Pop all the elements of the stack to the new min and push them back
    • Time complexity: O(2N)
    • Space complexity: O(N)

A better way

  • Instead of storing just the elements we can store a tuple on the stack
    • (val, currentMin)
  • But this makes the space complexity O(2N)

The desired way

  • This is the approach your interviewer wants
  • This is not something that can be discovered in an interview, unless someone is really lucky.
  • The intuition is that on push if the new element is smaller than the current min
    • store the new element in min
    • and store a modified value on the stack
      • modifiedVal = 2 * newVal - currentMin
  • stack.push(val)
    • If stack.empty()
      • Push val
      • minVal = val
    • If val < minVal
      • modifiedVal = 2 * val - minVal
      • Push modifiedVal on the stack
      • minVal = val
    • Else
      • Push val on the stack
    • Time complexity: O(1)
  • stack.min()
    • return minVal
    • Time complexity: O(1)
  • stack.top()
    • If stack.top() > stack.min()
      • return stack.top()
    • Else
      • newMin = 2 * minVal - stack.top()
      • return minVal
    • Time complexity: O(1)
  • stack.pop()
    • If stack.top() < stack.min()
      • `val = minVal
      • minVal = 2 * val - stack.pop()
      • return val
    • Else
      • return stack.pop()
    • Time complexity: O(1)

Refs