# 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]