The Low That Came Too Late

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

Domain
Python
Difficulty
easy
Seniority
mid
Asked in
Anaplan

Problem

A trading feed hands you a day's prices in the order they were captured, and we want the largest gain a single buy-then-sell could have booked. Buying has to happen before the sell, so a low that only appears after the day's high is off limits. Return 0 when no pair of moments would have turned a profit.

You only get to buy before you sell. Find the biggest gain the day allowed.

Example 1

Input:

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

Output:

5

Example 2

Input:

prices = [2,4,1,7]

Output:

6

Worked solution and explanation

Why this problem exists in real interviews

This is a maximum forward difference wearing a trading costume. The skill being probed: can you find the biggest later-minus-earlier gap in one left-to-right pass, while respecting that the buy must come before the sell? Almost everyone sees numbers and a word like 'profit' and writes max(prices) - min(prices). That is the trap. It answers a different question, one with no notion of time, and it silently pairs a low that showed up late with a high that came earlier. On a falling series like [7, 6, 4, 3, 1] it prints 6; the real answer is 0, because you never get to sell into that final 1.

Break down the requirements

Step 1: Carry the cheapest buy seen so far

Scan the prices front to back and keep one number: the smallest price up to and including where you stand. Because you only ever look backward for the buy, this value is always a legal purchase point for any sell that comes after it.

Step 2: Measure each price as a potential sell

At every position, the best gain you could book by selling right now is current_price minus the running minimum. Track the largest such gain across the whole pass. Order is preserved for free because the minimum only ever reflects earlier prices.

Step 3: Clamp the floor at zero

If prices only fall, no sell ever beats its buy, so the best gain stays 0. Starting the answer at 0 and only ever raising it handles the strictly decreasing case, the single element, and the empty feed without any special branch.

The solution

One pass, running minimum
def max_gain(prices):
    min_price = None
    best = 0
    for price in prices:
        if min_price is None or price < min_price:
            min_price = price
        elif price - min_price > best:
            best = price - min_price
    return best
The tempting one-liner (wrong)
max(prices) - min(prices). Fast to type, and right whenever the low happens to precede the high. But it has no concept of order, so on [7, 6, 4, 3, 1] it pairs the first 7 with the last 1 and reports 6, a sale that happens in the past.
Running minimum (correct)
The single pass never lets the sell reach back to a price that came after it, because min_price only summarizes what is already behind you. Same O(n) time, but it actually answers the buy-before-sell question.

Common follow-up questions