LeetCode 121 · Easy · Sliding Window

Best Time to Buy and Sell Stock

Given prices[i], the price of a stock on day i, return the biggest profit from buying on one day and selling on a later day, or 0 if no trade makes money.

O(n)time
O(1)space
1 passrunning minimum

comma-separated integers · 1–16 days · prices 0 to 999

public int maxProfit(int[] prices) { int minPrice = prices[0]; // cheapest buy so far int best = 0; for (int price : prices) { if (price < minPrice) { minPrice = price; // new cheapest day } int profit = price - minPrice; // sell today best = Math.max(best, profit); } return best;}
day
—
price
—
minPrice
—
profit
—
best
0

Why it works

  1. Brute force tries every (buy, sell) pair with the buy first: O(n²).
  2. Fix the sell day, and the best buy day is just the cheapest day before it. So carry one number, the running minimum, instead of rescanning the past.
  3. Invariant: after day i, minPrice is the lowest price in days 0..i and best is the best trade that sells by day i. One pass, two variables: O(n) time, O(1) space.
  4. Pitfall: the answer is not max − min of the whole array, because the max may come first. In [3,8,2,5,1,4] that gives 8 − 1 = 7, but you cannot sell on day 1 what you buy on day 4. A new minimum never resets best.
  5. Sliding-window view: NeetCode writes the same loop with l (buy) and r (sell), jumping l = r whenever prices[r] < prices[l]. There, prices[l] is minPrice.
  6. Follow-up, Stock II (122): unlimited trades. Then just add up every day-to-day rise.