Best Time to Buy and Sell Stock

Valid Anagram

Single Number

Find the best profit from one buy followed by one later sale.

Given daily stock prices, return the maximum profit from at most one transaction. The sale must occur after the purchase; return `0` when no profitable trade exists.

**Input / output**
- Input: `prices: integer[]`
- Output: non-negative integer profit

**Examples**
1. `[7,1,5,3,6,4]` returns `5` by buying at `1` and selling at `6`.
2. `[7,6,4,3,1]` returns `0`.

**Constraints**
- `0 <= prices.length <= 100,000`
- `0 <= prices[i] <= 1,000,000`

**Follow-up**
How would the state change for unlimited transactions or at most `k` transactions?

- You need choose one day to buy and a later day to sell.
- Profit is `sell_price - buy_price`.
- If every later price is lower, the best valid answer is `0` because you can skip the trade.

Understand the Goal

- A direct solution checks every possible buy day with every later sell day.
- This finds the correct answer, but it repeats a lot of work.
- With two nested loops, the time complexity is O(n²).

Consider the Brute Force Idea

- When scanning prices from left to right, the best buy day before today is simply the lowest price seen so far.
- For each current price, calculate the profit from selling today after buying at that lowest earlier price.
- Then update the best profit if today gives a better one.

Track the Cheapest Buy Price

- Initialize `min_price` to a very large value and `best` to `0`.
- For each price, first update the minimum price seen so far.
- Then compare the current possible profit against the best answer.

Build the One-Pass Loop

- The scan preserves the rule that buying happens before selling because `min_price` only comes from days already visited.
- Time complexity is O(n) because each price is processed once.
- Space complexity is O(1) because only two variables are stored.