Best Time to Buy and Sell Stock

What the problem is really asking

We are allowed exactly one buy and one sell.

So the real question is:

"For every day I could sell, what is the cheapest day I could have bought before it?"

Intuition

If today is the selling day, then only one thing matters from the past: the lowest price seen so far.

That means we do not need to remember every earlier price. We only need the best buying opportunity up to this point.

Brute-force idea

The direct solution is to try every pair of days:

• buy on day i
• sell on day j > i
• compute the profit
• keep the maximum

That works, but it takes O(n^2) time.

Optimized approach

Walk through the array once:

1. keep minPrice, the cheapest stock price seen so far
2. at each day, pretend we sell today
3. profit would be currentPrice - minPrice
4. update the best answer

Then move on.

This works because the best sale ending today must use the cheapest earlier buying price.

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int bestProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            bestProfit = Math.max(bestProfit, price - minPrice);
        }

        return bestProfit;
    }
}

Dry run

Take prices = [7, 1, 5, 3, 6, 4].

• start with minPrice = 7, bestProfit = 0
• see 1: update minPrice = 1
• see 5: profit is 5 - 1 = 4, so bestProfit = 4
• see 3: profit is 2, answer stays 4
• see 6: profit is 5, answer becomes 5
• see 4: profit is 3, answer stays 5

Final answer: 5.

Common mistakes

1. Selling before buying

You can only compare the current day with prices that happened earlier.

2. Resetting the answer when a lower price appears

A lower price only changes the future buying option. It does not erase earlier profits you already found.

3. Confusing this with the multiple-transactions version

This problem allows only one buy and one sell.

Complexity

Time Complexity: O(n)

Space Complexity: O(1)