Editorial: Best Time to Buy and Sell Stock

Overview

At its core, this problem asks us to find the maximum difference between two elements in an array, prices[j] - prices[i], with the strict constraint that the "buy" day i must come before the "sell" day j (i.e., i < j).

Because we cannot travel back in time to sell a stock before we bought it, the sequence of the array matters. If the array strictly decreases, it is impossible to make a profit, and we should return 0. Otherwise, we want to buy at the lowest possible valley and sell at the highest possible peak that follows that valley.

Brute Force

The most intuitive way to solve this is to simulate every possible trade. We can use two nested loops: the outer loop iterates through every possible buying day, and the inner loop iterates through every possible selling day that comes after the buying day.

For each pair of days, we calculate the potential profit. We keep track of the maximum profit seen across all combinations and return it at the end.

def best_time_to_buy_and_sell_stock(prices: list[int]) -> int:
    max_profit = 0
    n = len(prices)
    
    # i represents the day we buy
    for i in range(n):
        # j represents the day we sell (must be after i)
        for j in range(i + 1, n):
            current_profit = prices[j] - prices[i]
            if current_profit > max_profit:
                max_profit = current_profit
                
    return max_profit

• Time complexity: O(N^2) — where N is the number of days, because we check all possible pairs (i, j) resulting in N*(N-1)/2 iterations.
• Space complexity: O(1) — because we only use a single variable (max_profit) to keep track of the maximum profit, requiring constant extra memory.

Optimal Approach

The brute-force solution is too slow for large inputs (up to $10^5$ elements) and will likely result in a Time Limit Exceeded (TLE) error. We can optimize this to a single pass.

As we iterate through the array from left to right, we only really care about two things at any given day:

1. What is the cheapest price we could have bought the stock for up to this point?
2. If we sell the stock today, does it give us a better profit than our previous best?

We can maintain two variables: min_price (initialized to infinity) and max_profit (initialized to 0). On each day, we first update min_price if the current price is lower than our known minimum. If it isn't lower, we check if selling at the current price yields a higher profit than our current max_profit. By doing this, we guarantee that we are always calculating the profit using the lowest possible buy price that occurred prior to the current day.

def best_time_to_buy_and_sell_stock(prices: list[int]) -> int:
    max_profit = 0
    min_price = float('inf')
    
    for price in prices:
        # Update the minimum price encountered so far
        if price < min_price:
            min_price = price
        # Calculate profit if we sell today and update max_profit if it's better
        elif price - min_price > max_profit:
            max_profit = price - min_price
            
    return max_profit

• Time complexity: O(N) — where N is the number of days, because we iterate through the prices array exactly once.
• Space complexity: O(1) — because we only allocate two variables (max_profit and min_price) regardless of the size of the input array.

Edge Cases to Consider

• Continuously decreasing prices (e.g., [7, 6, 4, 3, 1]): The condition price < min_price will be triggered every day. The elif block evaluating profit will never execute, and max_profit will correctly remain 0.
• Short arrays: The constraints guarantee at least 1 element. If prices.length == 1, the loop executes once, min_price becomes that single price, and max_profit safely returns 0 since no sell day is possible.