# LeetCode 121: Best Time to Buy and Sell Stock

## Problem Restatement

We are given an array `prices`, where `prices[i]` is the stock price on day `i`.

We may choose one day to buy one stock and a later day to sell it. We need to return the maximum possible profit. If no profit is possible, return `0`. The official problem requires the selling day to be in the future after the buying day.

For example:

```python
prices = [7, 1, 5, 3, 6, 4]
```

The best choice is:

```text
buy at 1
sell at 6
```

The profit is:

```python
6 - 1 = 5
```

So the answer is:

```python
5
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of stock prices |
| Output | Maximum profit from one buy and one sell |
| Buy day | Must come before sell day |
| Transaction count | At most one transaction |
| No profit case | Return `0` |

The function shape is:

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        ...
```

## Examples

For:

```python
prices = [7, 1, 5, 3, 6, 4]
```

Possible profitable choices include:

```text
buy at 1, sell at 5 -> profit 4
buy at 1, sell at 3 -> profit 2
buy at 1, sell at 6 -> profit 5
buy at 3, sell at 6 -> profit 3
```

The best profit is:

```python
5
```

For:

```python
prices = [7, 6, 4, 3, 1]
```

The price only decreases.

There is no future day where selling gives a positive profit, so the answer is:

```python
0
```

## First Thought: Try Every Buy and Sell Day

The direct approach is to test every pair of days.

Choose a buy day `i`.

Choose a sell day `j`, where:

```python
j > i
```

Compute:

```python
prices[j] - prices[i]
```

Track the maximum profit.

This works, but it checks too many pairs.

For `n` prices, this takes:

```python
O(n^2)
```

We can do better.

## Key Insight

When we are at a possible selling day, the best buying day is the lowest price seen before today.

So while scanning from left to right, keep:

| Variable | Meaning |
|---|---|
| `min_price` | Lowest price seen so far |
| `best` | Best profit found so far |

For each price:

1. Treat it as the selling price.
2. Compute profit using the lowest earlier price.
3. Update the best profit.
4. Update the lowest price.

This respects the rule that we must buy before selling, because `min_price` only comes from days already scanned.

## Algorithm

Initialize:

```python
min_price = prices[0]
best = 0
```

Then scan every price:

1. Compute the profit if we sell today:

```python
price - min_price
```

2. Update the best profit.
3. Update `min_price` if today's price is lower.

Return `best`.

## Correctness

At each day, `min_price` stores the smallest stock price from all previous days and the current day.

If we sell on the current day, the best possible buying price is the smallest price seen before or on this day. Buying on the same day gives profit `0`, so it does not create an invalid positive profit.

The algorithm computes the best profit for each possible selling day using the best available earlier buying price. It then keeps the maximum among all such profits.

If prices always decrease, every computed profit is at most `0`, and `best` remains `0`.

Therefore, the algorithm returns the maximum profit possible from one valid transaction.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the prices once |
| Space | `O(1)` | We store only two variables |

## Implementation

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        best = 0

        for price in prices:
            best = max(best, price - min_price)
            min_price = min(min_price, price)

        return best
```

## Code Explanation

Start with the first price as the lowest price seen:

```python
min_price = prices[0]
```

No transaction has been made yet, so best profit starts at `0`:

```python
best = 0
```

For each price, compute the profit if we sell today:

```python
best = max(best, price - min_price)
```

Then update the minimum price:

```python
min_price = min(min_price, price)
```

Finally:

```python
return best
```

## Testing

```python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        best = 0

        for price in prices:
            best = max(best, price - min_price)
            min_price = min(min_price, price)

        return best

def run_tests():
    s = Solution()

    assert s.maxProfit([7, 1, 5, 3, 6, 4]) == 5

    assert s.maxProfit([7, 6, 4, 3, 1]) == 0

    assert s.maxProfit([1, 2]) == 1

    assert s.maxProfit([2, 1, 2, 0, 1]) == 1

    assert s.maxProfit([3, 3, 3]) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[7,1,5,3,6,4]` | Standard profitable case |
| `[7,6,4,3,1]` | No profit possible |
| `[1,2]` | Minimum profitable case |
| `[2,1,2,0,1]` | Confirms update order with later low price |
| `[3,3,3]` | Flat prices give zero profit |