best-time-to-buy-and-sell-stock

Difficulty: Easy  ·  Topic: Sliding Window  ·  Practice it on parikshan: /practice/best-time-to-buy-and-sell-stock/start

The story

You join Robinhood's onboarding team and your first toy assignment is the "Could-Have-Been" widget. The product team wants to show new users, on their dashboard, the maximum profit they could have made on AAPL last month, had they bought on the best day and sold on a later day. One transaction. The marketing copy reads "Imagine if you started a month ago." You are given the array of daily closing prices and must return that hypothetical max profit, or zero if no buy-sell pair was profitable.

That is best-time-to-buy-and-sell-stock. The framing screams "compare all pairs", but a single pass solves it.

What's actually being asked

Given an array prices of length n where prices[i] is the price on day i, return the maximum profit from one buy followed by one later sell. If no profit is possible, return 0.

The constraint sell strictly after buy (j > i) is the entire reason the trivial "max minus min" of the whole array is wrong: the min might come after the max.

The naive approach

Two loops. For every buy day i, for every sell day j > i, compute prices[j] - prices[i] and track the max. O(n^2). For n = 10^5, that is 10 billion. Times out.

The key insight

At each day i, the best you can possibly do if you sell today is prices[i] - min(prices[0..i-1]). So if you track the minimum-so-far as you walk left to right, every day you only need that one number to compute today's best sale. The overall answer is the maximum across all days.

This is a variable-length sliding window with a degenerate structure: the window is [buy_day, sell_day], and as you sweep sell_day forward, you greedily set buy_day to the cheapest day seen so far. Two pointers, but you do not need an explicit pair; just a running min_price is enough.

Step-by-step approach

1. Initialise min_price = prices[0], best = 0.
2. For i from 1 to n-1:
   • best = max(best, prices[i] - min_price).
   • min_price = min(min_price, prices[i]).
3. Print best.

Order matters: compute best before updating min_price, otherwise on a single-day improvement you would compare a price to itself and get zero when the real answer is positive. (Actually both orders are correct here because prices[i] - prices[i] is zero and never beats a positive best; but writing the before version makes the intent obvious.)

Worked example

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

Answer: 5 (buy at price 1 on day 1, sell at price 6 on day 4).

Complexity

• Time: O(n), one pass.
• Space: O(1), two scalars.

Common pitfalls

• max(prices) - min(prices) on the whole array: ignores the chronology. Returns 6 on [7, 1, 5, 3, 6, 4] correctly only by accident; on [6, 1] it returns 5 when the right answer is 0 (you cannot sell before you buy).
• Initialising best to prices[0] or to negative infinity: should be 0 since the problem allows you to skip the trade.
• Sorting the prices: completely destroys the chronological constraint. Yet agents do this if you only tell them "find the max difference".
• Confusing this with best-time-to-buy-and-sell-stock-ii (multiple transactions, where the answer is sum of all upward steps). Different problem, different algorithm.

Where this shows up in the enterprise

• Robinhood / Zerodha / E*TRADE retail dashboards: "best day to have bought" widgets, portfolio replay tools.
• Bloomberg terminals: maximum drawdown calculations (the dual: largest peak-to-trough drop).
• Citadel / Two Sigma / Jane Street backtests: single-trade theoretical-max benchmarks against which strategy returns are measured.
• AWS / GCP billing analysers: largest cost spike between a low and a later high in a billing-history chart.
• Google Ads / Meta Ads: largest CPM swing over a campaign window.
• CRM funnel analysis (Salesforce / HubSpot): largest stage-conversion improvement between two points in time.
• Performance regression tools at Uber / Lyft: largest p99-latency increase between a baseline and a later snapshot.

Any "biggest gain between two timestamps where the second is later than the first" is this problem.

Variants you'll see elsewhere

• best-time-to-buy-and-sell-stock-ii: unlimited transactions. Greedy sum of upward steps.
• best-time-to-buy-and-sell-stock-iii: at most two transactions. DP with four states.
• best-time-to-buy-and-sell-stock-iv: at most k transactions. DP with O(nk) or O(k) per day.
• maximum-subarray (Kadane): same one-pass "track running thing" pattern, but the running thing is the best-ending-here sum.
• largest-rectangle-in-histogram: stack-based, but solves "for each bar, find the widest left-min and right-min", a similar look-back-once idea.

How parikshan turns this into a learning loop

This is the second sliding-window problem the curriculum recommends after maximum-average-subarray-i. The dynamic private tests on parikshan will give you:

• A strictly increasing array (the answer is last - first).
• A strictly decreasing array (the answer is 0, not a negative number).
• An array of length 1 (one day, cannot buy and sell, answer is 0).
• An array of length 2 with prices[1] < prices[0] (no trade, answer is 0).
• A large array where the global min is on the last day (the answer is not max - min).

The integrity-scored AI sparring partner is most useful here to ask "why is greedily tracking min_price correct?", because the proof is short but non-obvious on the first read: when you compute prices[i] - min_price, you are computing the best profit ending at day i, and the overall best ending-day is the answer because every valid pair has some ending day. Once you internalise that lemma, every Kadane-shaped problem becomes easier.

In the AI-integrated workspace

When an agent writes a "max gain over a time series" function, your review checks:

1. Does it respect the chronological constraint? (Not max(arr) - min(arr).)
2. Is the running minimum updated after the answer-update, or are both updates split cleanly?
3. Does it clamp the answer at 0 for the no-profit case?
4. Does the function handle n = 0 and n = 1 without indexing past the array?

A surprising number of LLM-generated "stock profit" snippets pass the sample input and fail on [2, 1] because they assume the answer is last - first. That single test case separates a correct solution from a plausible-looking one. parikshan's dynamic private tests will include it; you do not need to remind your future agent, you just need to recognise the failure mode when you read the diff.