Finding minumum element in a stack in constant time

Question

If I want to find a minimum element in a stack (integer key), in constant time then it can be done as 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

for key in arr:
    push(key)    

In the above solution it is possible to find out min value element in O(1) but it uses an auxiliary memory of size n.

Is there a way that It can be done without using a n size memory or say constant memory, by exploiting arithmetical properties of the integer key.

Answer 1

You can do it in O(1) without O(n) memory if you only want to store a single min value of all the pushed elements.

If you want to store a history of min elements, then there is no other way but to use a auxiliary data structure to hold them. In that case, using the stack is optimal since you can push/pop in O(1) time, which is the method you are using.

Aside: your code contains a tiny bug:

With your array arr = [2, 2] after 2 pushes, min_stack = [2]

When you pop the first time, min_stack = [] and main_stack = [2] So get_min() will return None, not 2.

To fix it, change push_key:

 if len(min_stack) < 1 or min_stack[-1] >= key: