python - Finding minumum element in a stack in constant time -

if want find minimum element in stack (integer key), in constant time can done following:

arr = [ 10, 7, 15, 12, 5 ]   min_stack = [] main_stack = []  def get_min():     if len(min_stack) < 1:         return none     return min_stack[-1]  def push(key):     main_stack.append(key)     if len(min_stack) < 1 or min_stack[-1] > key:         min_stack.append(key)   def pop():     key = main_stack.pop()     min = get_min()     if key == min:         min_stack.pop()     return key  key in arr:     push(key)     

in above solution possible find out min value element in o(1) uses auxiliary memory of size n.

is there way can done without using n size memory or constant memory, exploiting arithmetical properties of integer key.

since wasn't stated otherwise, figured include solution if range of integers being pushed onto stack limited 32bit on 64bit system.

i know these constraints may not applicable, leave here in case gives rise other ideas.

note if stack values not restricted being integers tuple used in similar fashion push of x push of (min_thus_far, x) example.

arr = [10, 7, 15, 12, 3, 21]  main_stack = []  def get_min():     if len(main_stack) == 0:         return none     return main_stack[-1] >> 32  def push(key):     current_min = get_min()     if current_min:         if key < current_min:             current_min = key     else:         current_min = key     main_stack.append(key + (current_min << 32))  def pop():     key = main_stack.pop()     return key & 0xffffffff  key in arr:     push(key)  def print_state():     print(", ".join(str(x & 0xffffffff) x in main_stack))     print("min: %d" %(get_min(),))  _ in arr:     print_state()     print "popped:", pop() 

output:

10, 7, 15, 12, 3, 21 min: 3 popped: 21 10, 7, 15, 12, 3 min: 3 popped: 3 10, 7, 15, 12 min: 7 popped: 12 10, 7, 15 min: 7 popped: 15 10, 7 min: 7 popped: 7 10 min: 10 popped: 10 

and here tuple version:

arr = [10, 7, 15, 12, 3, 21]  main_stack = []  def get_min():     if len(main_stack) == 0:         return none     return main_stack[-1][0]  def push(key):     current_min = get_min()     if current_min:         if key < current_min:             current_min = key     else:         current_min = key     main_stack.append((current_min, key))  def pop():     key = main_stack.pop()     return key[1]  key in arr:     push(key)  def print_state():     print(", ".join(str(x[1]) x in main_stack))     print("min: %d" %(get_min(),))  _ in arr:     print_state()     print "popped:", pop()