Monday, December 19, 2011

Use some Datastructure to get 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

0 comments:

Post a Comment