O(1) stack operations.

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 !!