Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal.
Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does.
Insight : compress the information using diff
PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)
POP :
min = pop()
elem = pop()
if elem is -ve
push(min-elem) // earlier min
return min
else
push(min)
return elem + min
MIN :
min = pop()
push(min)
return min
O(n+1) space and constant operations for pop push min