Best Time to Buy and Sell Stock

Easy#121lowest price so far

You get a share's price for each day. Buy it on one day and sell it on a later day, once. Return the largest profit you can make, or 0 if every trade loses. Our example: [4, 10, 7, 2, 9, 1, 3] — the answer is 7: buy at 2 on day 3, sell at 9 on day 4.

121 Best Time to Buy and Sell StockWalkthrough · 1×

Example: [4, 10, 7, 2, 9, 1, 3]. Watch day 3: the price drops to 2 after a profit of 6 is already found; selling at 9 the next day beats it.

pricelowbest0411027324951634
this stepthe day low was paid onread fromanswer: buy and sell

Day 0: the only price to buy at so far is 4, low = 4

01/27
restart · back · play · step
Speed
1function maxProfit(prices):
2 low = prices[0] // lowest price so far
3 best = 0
4 for i from 1 to len(prices) - 1:
5 profit = prices[i] - low // sell today
6 best = max(best, profit)
7 low = min(low, prices[i])
8 return best
state
i
–
low
4
profit
–
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. If you sell on day i, the best buy is the lowest price before it. low keeps exactly that, so each day needs one subtraction, not a look back over all earlier days.
  2. A new low does not erase best: an earlier sale stays a valid trade. Here best keeps 6 while low drops to 2, and only the sale at 9 replaces it.
  3. The answer is not the highest price minus the lowest: the sale has to come after the buy. 10 comes before 2, and after 1 the price never climbs above 3.

Complexity

Time O(n): one pass over the days, constant work per day. Memory O(1): only low and best; the rows in the picture show their history.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.