The Stock Span Problem

In [1]:
def stack_create():
    return []

def stack_push(stack, value):
    stack.append(value)

def stack_pop(stack):
    return stack.pop()

def stack_top(stack):
    return stack[-1]

def stack_is_empty(stack):
    return len(stack) == 0

def stack_to_string(stack):
    s  = " TOP OF THE STACK\n"
    s += "-------------------\n"
    
    for v in reversed(stack):
        s += str(v).center(20) + "\n"

    s += "-------------------\n"
    s += "BOTTOM OF THE STACK\n"
    return s
In [2]:
p = [100, 80, 60, 70, 60, 75, 85]
In [3]:
def compute_span(prices):
    s = []
    
    # Traverse the list of prices
    for i, price in enumerate(prices):
        # For each price, traverse all the previous prices,
        # incrementing S_i until we encounter a price that
        # is larger than the current price.
        s_i = 0
        for prev_price in prices[i::-1]:           
            if prev_price > price:
                break
            else:
                s_i += 1
                
        s.append(s_i)
                
    return s
In [4]:
compute_span(p)
Out[4]:
[1, 1, 1, 2, 1, 4, 6]
In [5]:
# Stack-based implementation of the stock span problem.
# Notice how we only use the stack functions when interacting
# with the stack. We never access the values in the 'st' list
# directly.
def compute_span_stacks(prices):
    s = []
    
    # Create a stack
    st = stack_create()
    
    # Traverse the list of prices
    for i, price in enumerate(prices):
        
        # Pop elements from stack until we encounter a price that
        # is greater than the current price, or until the stack
        # is empty
        while not stack_is_empty(st):
            prev_price = prices[stack_top(st)]
            
            if prev_price > price:
                break
            else:
                stack_pop(st)
    
        if stack_is_empty(st):
            # If the stack is empty, then the current price
            # is greater than all the elements to the left of
            # it (note: this is trivially true for the first
            # price in the list)
            s_i = i + 1
        else:
            # Otherwise, the current price is only greater than the
            # elements after the index at the top of the stack.
            s_i = i - stack_top(st)
               
        s.append(s_i)
                
        # Push the index of this price into the stack
        stack_push(st, i)
        
    return s
In [6]:
compute_span_stacks(p)
Out[6]:
[1, 1, 1, 2, 1, 4, 6]