Push a value and a min
Updated
On push(x), newMin = empty ? x : min(x, currentMin). Push the pair (x, newMin). Peek.min is then getMin in O(1). The buried pairs keep older mins for after pops.
What to focus on
Pushing a new min records it. Pushing a larger value copies the old min into the new pair. Do not mutate buried pairs.
Worked examples
new min
a = [(4,4)], push 1- min(1,4)=1
- push (1,1)
Result: [(4,4), (1,1)]
keep min
a = [(4,4), (1,1)], push 9- min(9,1)=1
- push (9,1)
Result: [(4,4), (1,1), (9,1)]
first
a = [], push 4- newMin=4
Result: [(4,4)]
Try it
Write pushMin(a, x). a is the stack of (value, min) pairs. x is the integer to push. Push (x, min(x, currentMin)), or (x, x) if empty. Do not mutate buried pairs. Push 4,1,9 as pairs. After 1 the min is 1. After 9 it stays 1. First push onto [] uses x as min.
Values are integers. You may push onto an empty min-stack.