HARD Lab · Arrays & Hashing · 02

121. Best Time to Buy and Sell Stock

Given daily prices, find the maximum profit from one buy-then-sell transaction. The key is a single greedy pass: always buy at the cheapest price seen so farand ask “what would I profit if I sold today?” — updating the best answer whenever a new high margin appears.

● EasyGreedyOne PassTypeScript

PROBLEM What we're solving

Given an array prices where prices[i] is the stock price on day i, return the maximum profit from buying on one day and selling on a later day. You must buy before you sell. If no profit is possible, return 0.

Example: prices = [7, 1, 5, 3, 6, 4]. Buy on day 1 (price 1), sell on day 4 (price 6) → profit = 5. Buying on day 0 and selling on day 2 only yields -2— you can't sell before you buy.

KEY IDEA Buy low before, sell high after

Insight → For every day you consider as the sell day, the best buy day is the cheapest day strictly before it. You never need to look ahead — just keep a running minimum. As you scan left to right, maintain minPrice(cheapest buy seen) and ask “profit if I sell today = price − minPrice”. Update maxProfit whenever that beats the current best. One pass, constant space.

RECIPE One-pass greedy scan

  • 0 · Initialize. Set minPrice = Infinity and maxProfit = 0. The zero default handles the “no profitable trade” case automatically.
  • 1 · Scan each price. For every price in the array:
  • 1a · New low? If price < minPrice, update minPrice = price. This day becomes the new candidate buy day.
  • 1b · New high profit? Otherwise compute profit = price − minPrice. If it beats maxProfit, update it. We can't update both in the same step because buying and selling on the same day yields zero profit.
  • 2 · Return maxProfit. Guaranteed ≥ 0.
Classic confusion → Some people try to track both the buy and sell indices explicitly, or use a nested loop checking every pair. Neither is needed. You only ever care about the single cheapest price to the left of the current day — a running minimum captures that in O(1). The nested loop approach is O(n²) and will TLE on large inputs.

COST Complexity & alternatives

Check every pair (brute force)
O(n²)
Two nested loops; TLEs on large inputs.
One-pass greedy scan
O(n)
O(n) time; O(1) extra space.

Why greedy is safe here

Because you can only buy before you sell, the optimal buy day for any sell day i is simply min(prices[0..i-1]). Maintaining that running minimum greedily is both correct and optimal.

Pattern transfer → This “track best-so-far” idea recurs in Best Time to Buy and Sell Stock II (multiple transactions — greedy on every uptick), Maximum Subarray(Kadane's is the same one-pass running-best idea), and Trapping Rain Water (left-max + right-max arrays).

RUN IT Scan once: track the cheapest buy, best sell

step 0 / 7
STARTPrices: [7, 1, 5, 3, 6, 4]. We scan left→right, tracking the minimum price seen so far (buy day) and the best profit we could lock in today (sell day).
7
0
1
1
5
2
3
3
6
4
4
5
minPrice
∞
maxProfit
0
current daymin price so far (buy)best sell day
slowfast

TYPESCRIPT The solution, annotated

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

  for (const price of prices) {
    if (price < minPrice) {
      minPrice = price;          // found a cheaper buy day
    } else {
      const profit = price - minPrice;
      if (profit > maxProfit) {
        maxProfit = profit;      // found a better sell day
      }
    }
  }

  return maxProfit;
}

Reading it block by block

Lines 2–3 — initialize trackers. minPrice = Infinity so the very first price always sets the initial minimum. maxProfit = 0 is the correct default when no profitable trade exists.
Lines 5–8 — update the buy candidate.If today's price is lower than any seen before, record it as the new cheapest buy day. We cannot also sell on this day (profit would be zero), so we move on.
Lines 9–13 — evaluate sell profit. We already have the cheapest possible buy price to our left. price - minPrice is the profit if we sold today. Update maxProfitif it's better.
Line 17 — return result. After one pass the answer is in maxProfit. Because it was initialized to 0and never goes negative, this handles the “prices only decrease” edge case automatically.
Complexity → O(n) time — one pass through the array. O(1) extra space — only two scalar variables regardless of input size.

INTERVIEWFollow-ups they'll ask

  • “What if prices are all decreasing?” maxProfit stays 0 (never updated) and we correctly return 0.
  • “What if we can make multiple transactions (LC 122)?” Greedily add every positive day-over-day difference — if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1].
  • “At most k transactions (LC 123 / 188)?” Switch to DP with state dp[k][hold] tracking best profit with k buys and current hold state.
  • “With a cooldown day (LC 309)?” DP with states held, sold, resttracking which state we're in each day.
  • “Can you return the buy and sell days, not just the profit?” Yes — also track bestBuy and bestSell indices and update them whenever maxProfit improves.

MNEMONIC The one-liner

"Track the valley: minPrice chases the lowest buy, maxProfit chases the highest spread."

TRIGGERS When you see ___ → reach for ___

"buy before sell, maximize profit"one-pass running minimum
best previous element for each positionmaintain a running min/max
"prices only go down" edge caseinitialize maxProfit = 0, return 0
follow-up: multiple transactionssum all positive consecutive differences

SKELETON The reusable shape

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

  for (const price of prices) {
    if (price < minPrice) {
      minPrice = price;
    } else {
      const profit = price - minPrice;
      if (profit > maxProfit) maxProfit = profit;
    }
  }

  return maxProfit;
}

FLASHCARDS Tap to flip

What two values do you track in the one-pass solution?
minPrice (cheapest buy seen so far) and maxProfit (best spread locked in so far).
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the time complexity of the one-pass greedy solution for maxProfit?
QUESTION 02
For prices = [7, 6, 4, 3, 1], what should the function return?
QUESTION 03
Why do we use an if/else (not two separate ifs) when updating minPrice and maxProfit?
QUESTION 04
Which value should minPrice be initialized to?
QUESTION 05
prices = [2, 4, 1, 7]. What is the maximum profit and on which days do you buy/sell?
QUESTION 06
How does this problem relate to Maximum Subarray (Kadane's algorithm)?
QUESTION 07
If allowed unlimited transactions (LC 122 variant), what is the simplest strategy?