121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a single share on day i.
You get to make at most one trade: pick a day to buy the share, then pick a later day to sell it. Return the biggest profit that trade can earn. If no buy/sell pair makes money, skip the trade entirely and return 0.
Note that you cannot sell before you buy — time only moves forward.
Example 1:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 1 when the price is 1 and sell on day 4 when it hits 6, for a profit of 6 - 1 = 5. Buying at 1 and selling at 5 only earns 4, and you cannot pair the 7 with the 1 because the 7 comes first.
Example 2:
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: The price only falls, so every possible trade loses money. The best move is to make no trade at all, which earns 0.
Constraints:
- 1 ≤ prices.length ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁴
Hints:
A profit is always sell price minus buy price with the buy strictly earlier. Trying every (buy day, sell day) pair works but costs O(n²).
Walk the days left to right. If you sold today, the best buy would have been the cheapest price seen so far — track that minimum as you go and you never need a second loop.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: prices = [7, 1, 5, 3, 6, 4]
Expected output: 5