Best Time to Buy and Sell Stock

How it works

As we scan through the prices, we keep track of two things:

1. The lowest price so far → this is the best day to buy.
2. The best profit so far → selling today minus the lowest buy price seen earlier.

At each price, we imagine selling on that day.
The profit would be:
current price – lowest price seen so far

We then update:

• the maximum profit,
• and the lowest price if we find a cheaper one.

This way, we make the optimal buy–sell decision in one simple pass.

Steps

1. Initialize:
   • minBuy as the first price
   • maxP = 0 for the best profit
2. Loop through each price sell:
   • Update maxP with sell - minBuy.
   • Update minBuy if we find a smaller price.
3. Return maxP after scanning all days.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Selling Before Buying

The sell day must come after the buy day. Calculating prices[i] - prices[j] where j > i means you're selling in the past, which is invalid.

Returning Negative Profit

If prices only decrease, the maximum profit is 0 (don't trade), not a negative number. Always ensure the result is at least 0.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxP = 0
        minBuy = prices[0]

        for sell in prices:
            maxP = max(maxP, sell - minBuy)
            minBuy = min(minBuy, sell)
        return maxP

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxP = 0;
        int minBuy = prices[0];

        for (int& sell : prices) {
            maxP = max(maxP, sell - minBuy);
            minBuy = min(minBuy, sell);
        }
        return maxP;
    }
};