Best Time to Buy and Sell Stock

The problem

Array prices where prices[i] is the stock price on day i. Choose one day to buy and a later day to sell. Maximize profit. If you can’t profit, return 0.

Input:  [7, 1, 5, 3, 6, 4]
Output: 5   // buy at 1, sell at 6

Exactly one transaction (buy once, sell once). Not the multi-trade versions.

Brute force

Try every buy day i and every sell day j > i.

function maxProfitBrute(prices: number[]): number {
  let best = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      best = Math.max(best, prices[j] - prices[i]);
    }
  }
  return best;
}

Time	O(n²)
Space	O(1)

Fine for n ≤ a few hundred. Interviewers expect better.

Optimal: min so far + max profit

As you scan left → right:

• Keep minPrice = cheapest price seen so far (best buy so far)
• At day i, candidate profit = prices[i] - minPrice
• Update maxProfit
• Then update minPrice if today is cheaper

function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const p of prices) {
    if (p < minPrice) minPrice = p;
    else maxProfit = Math.max(maxProfit, p - minPrice);
  }

  return maxProfit;
}

Time	O(n)
Space	O(1)

Walk [7,1,5,3,6,4]

day	price	minPrice	profit cand	maxProfit
0	7	7	0	0
1	1	1	0	0
2	5	1	4	4
3	3	1	2	4
4	6	1	5	5
5	4	1	3	5

Why not “buy lowest, sell highest” globally?

Lowest may occur after the highest. Example [2, 4, 1] — global min is 1 at the end; correct answer is buy 2 sell 4 → profit 2. The running min respects time order.

Edge cases

• Empty / single day → 0
• Strictly decreasing → 0
• Strictly increasing → last − first
• Duplicates / flat prices → 0

Common mistakes

• Allowing sell before buy
• Using two independent min/max indices
• Confusing with II (unlimited trades) or III (at most two)

Follow-ups (name them)

1. II — unlimited transactions → sum every uphill step
2. With cooldown / fee → DP states
3. At most k transactions → DP

Interview delivery

1. One buy, one sell, later day.
2. Brute O(n²), then min-tracking O(n).
3. Trace decreasing array → 0.
4. State O(n)/O(1).

Related

• Jump Game — greedy scan patterns
• Container With Most Water
• House Robber — linear DP cousin
• Two Sum
• JavaScript Interview Guide

Further reading

• LeetCode 121 — Best Time to Buy and Sell Stock
• Kadane’s algorithm (related max subarray framing)