Min stack: a stack that knows its smallest value
Coding problemMediumAsked in: Adobe, Amazon, Flipkart, Goldman Sachs, Microsoft, Walmart
Build a stack that can also report its smallest value, with every command taking constant time. Your function receives a list of commands and runs them in order on an empty stack:
"push x"puts the value x on top;"pop"removes the top value (it outputs nothing);"top"outputs the top value;"min"outputs the smallest value currently in the stack.
Return all outputs, in order. "pop", "top" and "min" are only given when the stack is not empty.
Examples
Example 1
Input: commands = ["push -2","push 0","push -3","min","pop","top","min"]
Output: [-3,0,-2]
Example 2
Input: commands = ["push 5","push 5","pop","min"]
Output: [5]
A copy of 5 is still in the stack after one pop.
Example 3
Input: commands = ["push 1","top","min"]
Output: [1,1]
Constraints
- Between 1 and 100,000 commands
- Every pushed value is between -1,000,000,000 and 1,000,000,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.