DSA

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 https://leetcode.com/problems/min-stack/