Best Time to Buy and Sell Stock

Problem Description

You are given an array prices where prices[i] is the price of a stock on day i.

Choose a single day to buy and a later day to sell to maximize profit. Return the maximum profit achievable. If no profit is possible, return 0.

Examples

Constraints

• 1 ≤ prices.length ≤ 10⁵
• 0 ≤ prices[i] ≤ 10⁴

You Only Need to Remember the Cheapest Buy Day So Far

The brute force checks every pair (buy day, sell day). The insight: for any sell day i, the best possible buy day is whichever previous day had the lowest price. You don’t need to re-scan backwards; just track the minimum price as you go. Each day’s best profit is prices[i] - minPrice. Keep the running maximum of that.

This is the sliding window pattern: minPrice is the left boundary, i is the right, and the window always represents the current best buy position.

Solution 1: Brute Force

Check every pair of buy and sell days.

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int buy = 0; buy < prices.length; buy++) {
            for (int sell = buy + 1; sell < prices.length; sell++) {
                maxProfit = Math.max(maxProfit, prices[sell] - prices[buy]);
            }
        }
        return maxProfit;
    }
}

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        max_profit = 0
        for buy in range(len(prices)):
            for sell in range(buy + 1, len(prices)):
                max_profit = max(max_profit, prices[sell] - prices[buy])
        return max_profit

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        int maxProfit = 0;
        for (int buy = 0; buy < prices.size(); buy++)
            for (int sell = buy + 1; sell < prices.size(); sell++)
                maxProfit = std::max(maxProfit, prices[sell] - prices[buy]);
        return maxProfit;
    }
};

Complexity Analysis:

• Time Complexity: O(n²). Two nested loops.
• Space Complexity: O(1). No extra storage.

Where it breaks: at n = 10⁵, this is 5 billion iterations. Doesn’t pass.

Solution 2: One Pass (Track Minimum Price)

Walk through prices once. At each day, check if selling gives a new max profit. Update the minimum buy price if today is cheaper.

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;  // found a cheaper buy day, shift the window left
            } else {
                maxProfit = Math.max(maxProfit, price - minPrice);
            }
        }
        return maxProfit;
    }
}

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            if price < min_price:
                min_price = price  # found a cheaper buy day, shift the window left
            else:
                max_profit = max(max_profit, price - min_price)
        return max_profit

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        int minPrice = INT_MAX, maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;  // found a cheaper buy day, shift the window left
            } else {
                maxProfit = std::max(maxProfit, price - minPrice);
            }
        }
        return maxProfit;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Single pass through prices.
• Space Complexity: O(1). Two variables: minPrice and maxProfit.

Where it breaks: this only handles a single buy-sell transaction. If the problem extends to multiple transactions (LeetCode 122), you’d track profit differently by accumulating gains from every ascending day.

Why Not Track the Maximum Price Instead?

You might think: track the maximum price and subtract the minimum. That fails because you can’t sell before you buy. The max might come before the min in the array. You have to track the minimum price seen so far before each sell day, which is what the left-to-right scan enforces.

Common Mistakes

• Using the global max minus the global min. The maximum must come after the minimum. prices = [3, 1, 4] gives max=4, min=1, difference=3, which happens to be correct. But prices = [4, 1, 3] gives the same max and min, same difference of 3, but the correct answer is 2 (buy at 1, sell at 3). The global approach gets lucky in some cases.
• Returning a negative number. Initialize maxProfit = 0, not to prices[1] - prices[0]. If prices only decrease, no transaction should happen, so the answer is 0.
• Updating minPrice and computing profit in the same step. If today is both a new minimum and theoretically a sell day, you’d compute a profit of 0 (selling and buying the same day). The if/else or checking before updating prevents this.

Frequently Asked Questions

What if all prices are the same? minPrice stays at that price, and price - minPrice is always 0. maxProfit stays 0. Correct.

How does this extend to buying and selling multiple times? For unlimited transactions (LeetCode 122), add up max(0, prices[i] - prices[i-1]) for every day. Each positive difference is a profitable one-day trade.

What if the array has only one element? The loop runs once, doesn’t enter the else branch, and maxProfit stays 0. Correct, since you can’t sell on a day you buy.

← All Problems