Best Time to Buy and Sell Stock

Buy once, sell once later, maximise profit. Scan left to right keeping the cheapest price so far; selling today earns price - minSoFar. The best of those is the answer.

Traced input: prices = [7, 1, 5, 3, 6, 4] → 5. Original problem: neetcode.io/problems/buy-and-sell-crypto

Complexity

One pass, two variables.

Key idea

• The best sell day for today is fixed; the only question is the cheapest earlier buy day.
• Keep minPrice as you go, so that question is O(1).
• If prices only fall, the best profit stays 0 (don't trade).

Common mistakes

• Selling before buying: the min must come from earlier days only.
• Initialising profit to a negative number; the answer is never below 0.
• Tracking the global max and min separately ignores their order.

Solution

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int i = 0; i < prices.length; i++) {
        minPrice = Math.min(minPrice, prices[i]);
        best = Math.max(best, prices[i] - minPrice);
    }
    return best;
}

def maxProfit(prices: List[int]) -> int:
    min_price, best = float("inf"), 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX, best = 0;
    for (int p : prices) {
        minPrice = min(minPrice, p);
        best = max(best, p - minPrice);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.