The Market Timer

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
L3
Asked in
Integral Ad Science

Problem

A prices list holds one share price per trading day in chronological order. Return the largest gain from buying on one day and selling on a strictly later day, or 0 when no later day sells higher than an earlier one.

Buy low, sell later. The whole game is when.

Example 1

Input:

prices = [7,1,5,3,6,4]

Output:

5

Example 2

Input:

prices = [7,6,4,3,1]

Output:

0

Worked solution and explanation

What this really is

This is a running-minimum scan wearing a stock-trading costume. As you walk the prices once, left to right, the only question that matters at each day is: what is the most I could make if I sold today? The cheapest price you have seen so far is your buy candidate, and today's price minus that low is the profit on the table. The trap is the word *later*: the buy must come before the sell, so you can never sort the list or peek ahead. Candidates who reach for max(prices) - min(prices) walk straight into selling before they bought.

Walking it once

Step 1: Track the cheapest day so far

Seed the running minimum with the first price, then for every following day ask whether this price is a new low. A new low never sells; it only improves your future buy. That is why you update the minimum and move on rather than computing a profit on that same day.

Step 2: Score selling today

When today is not a new low, the candidate profit is today's price minus the running minimum. Keep it only if it beats the best you have banked. This is the one comparison that does the real work.

Step 3: Default to no trade

Start the best profit at 0 and never let it go negative. If prices only fall, no day ever beats the running minimum and you return 0 for free, exactly what the prompt asks.

The solution

Single pass with a running minimum
def max_stock_profit_once(prices: list[int]) -> int:
    if not prices:
        return 0
    min_price = prices[0]
    best_profit = 0
    for price in prices[1:]:
        if price < min_price:
            min_price = price
        elif price - min_price > best_profit:
            best_profit = price - min_price
    return best_profit

Buy candidate and best profit both fall out of one left-to-right scan.

Common follow-up questions