# The Low That Came Too Late > You only get to buy before you sell. Find the biggest gain the day allowed. Canonical URL: Domain: Python · Difficulty: easy · Seniority: mid ## 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. ## 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** ```python 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. > **Complexity** > > O(n) time, one pass, and O(1) extra space: two scalars regardless of how many ticks arrive. This is the shape you want for an intraday feed with hundreds of thousands of prints; nothing is sorted, nothing is stored. > **Interviewers Watch For** > > Whether you state the buy-before-sell constraint out loud and reject max-minus-min before writing it, and whether your answer is 0 (not a negative number) when prices only fall. Naming the invariant, that min_price is always a legal earlier buy, is the sentence that signals you actually understand why the single pass is correct. > **Common Pitfall** > > Seeding best with prices[0] - prices[0] but seeding min_price to a hardcoded 0 or a huge constant, then returning a bogus gain on an empty or single-element feed. Guarding min_price with None and starting best at 0 keeps every degenerate input honest. --- ## Common follow-up questions - Now return the buy and sell indices, not just the gain. What has to change? _(Tests tracking the index of the running minimum and the index where best was last improved, without a second pass.)_ - Allow up to two non-overlapping buy-sell transactions. How does your approach evolve? _(Pushes toward the classic four-state DP; checks whether the candidate can generalize past a single transaction.)_ - The prices arrive as an unbounded stream you can only read once. Does your solution still hold? _(Tests recognition that the running-minimum pass is already online and O(1) space, needing no buffering.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the-low-that-came-too-late) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.