The Market Streak

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

You have a stock's daily closing prices in prices, oldest first. For each day, report how many consecutive days up to and including that day had a price no greater than that day's price; the run ends the moment an earlier day was more expensive. Return one count per day in the same order, and every day counts at least itself.

Some stocks run longer than you think.

Example 1

Input:

prices = [100,80,60,70,60,75,85]

Output:

[1,1,1,2,1,4,6]

Example 2

Input:

prices = [10,20,30]

Output:

[1,2,3]

Worked solution and explanation

What this really is

Strip the market costume off and this is the classic stock-span problem: for each position, how far back does an unbroken run of no-bigger values reach. Almost everyone reaches for the brute force first, walking backward from each day until they hit a taller price. That is O(n squared), and on a strictly decreasing series it does the full triangle of work. The move the interviewer is actually waiting for: notice that once a day is swallowed by a later, taller-or-equal day, it can never bound any future span again, so you never need to look at it twice.

How the run gets measured

Step 1: Set up the stack and result

Start every day's span at the assumption it stands alone; the index stack starts empty. The stack will only ever hold days in strictly decreasing price order, which is the invariant doing the real work.

Step 2: Pop everything today swallows

While the top-of-stack day has a price no greater than today's, pop it. Those days are now part of today's run and are no longer candidates to ever stop a future run, so they leave for good.

Step 3: Read the span off what survives

If the stack emptied out, every earlier day was no greater, so the span is i + 1: the whole history up to here. Otherwise the surviving top index is the nearest taller day, and the span is the gap i minus that index.

Step 4: Leave today on the stack

Push today's index. It becomes the new open day that future, taller days will eventually swallow or stop against.

The solution

Monotonic index stack
def stock_span(prices: list) -> list:
    spans = [0] * len(prices)
    stack = []  # indices of days still 'open', strictly decreasing in price
    for i in range(len(prices)):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        spans[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return spans

Common follow-up questions