Leetcode 121. Best Time to Buy and Sell Stock

Let's understand what we're being asked to do. We have an array of daily stock prices like [7, 1, 5, 3, 6, 4] where each element represents the price on that day.

We need to find the maximum profit from buying on one day and selling on a later day. For example, if we buy at price 1 (day 1) and sell at price 6 (day 4), our profit is 6 - 1 = 5.

Important constraint: We must buy BEFORE we sell (i.e., j > i where i is buy day and j is sell day). We can't sell before buying!

Edge cases to consider: What if prices only decrease (like [7, 6, 4, 3, 1])? Then no positive profit is possible, so return 0. What if the array has only one price? Can't make any transaction, return 0.

The brute force approach checks all possible buy-sell pairs using nested loops. For each potential buying day i, iterate through all subsequent days j where j > i, calculate the profit prices[j] - prices[i], and track the maximum profit found. This approach is straightforward but inefficient because it examines every possible transaction pair.

def max_profit(prices):
    """
    Brute force approach: Check all possible buy-sell pairs.
    For each buying day i, check all subsequent selling days j where j > i.
    Track the maximum profit found across all pairs.
    """
    # Edge case: empty or single element array
    if len(prices) <= 1:
        return 0
    
    max_profit = 0
    
    # Outer loop: iterate through each potential buying day
    for i in range(len(prices)):
        # Inner loop: iterate through each potential selling day after buying day
        for j in range(i + 1, len(prices)):
            # Calculate profit for this buy-sell pair
            profit = prices[j] - prices[i]
            
            # Update maximum profit if current profit is better
            if profit > max_profit:
                max_profit = profit
    
    return max_profit

For each potential selling day, the best profit would come from buying at the lowest price seen so far before that day.

As we scan through prices, we can track the minimum price encountered up to the current point. Then for each price, we calculate what profit we'd get if we sold today (current price minus the minimum so far).

This transforms the problem from checking all possible buy-sell pairs (which would require nested loops) into a single pass through the array.

By maintaining the running minimum, we're essentially asking at each step: 'If I sell today, what's the best I could have done by buying earlier?'

Imagine you're watching stock prices day by day. You want to remember the cheapest price you've seen so far (that's your best buying opportunity).

Each new day, you ask: 'If I sold today at the current price, and I had bought at the cheapest price I've seen, what would my profit be?' Keep track of the maximum profit across all days.

This way, you're always comparing today's price against the best possible buying price from the past.

The optimal approach uses a single pass through the array while maintaining two variables: the minimum price seen so far and the maximum profit found so far. For each price, we first update the maximum profit by comparing it with the profit we'd get if we sold at the current price (current price minus minimum price). Then we update the minimum price if the current price is lower. This ensures we always consider the best possible buying opportunity for each selling day.

def max_profit(prices):
    """
    Find maximum profit from one buy-sell transaction.
    Uses single pass with running minimum price tracking.
    """
    if not prices or len(prices) < 2:
        return 0
    
    # Track minimum price seen so far and maximum profit
    min_price = prices[0]
    max_profit = 0
    
    # Iterate through prices starting from second day
    for current_price in prices[1:]:
        # Calculate profit if we sell at current price
        potential_profit = current_price - min_price
        
        # Update maximum profit if current is better
        max_profit = max(max_profit, potential_profit)
        
        # Update minimum price if current is lower
        min_price = min(min_price, current_price)
    
    return max_profit

• Single-pass tracking pattern: When looking for optimal differences in arrays (max profit, max subarray), maintain a running minimum/maximum as you iterate - this transforms an O(n²) nested loop problem into O(n) by tracking the best candidate seen so far instead of rechecking all previous elements.
• Greedy state maintenance: Keep track of the minimum price encountered so far and calculate potential profit at each step - this works because the optimal solution only requires knowing the lowest buy point before the current sell point, not the entire price history.
• Two-variable optimization technique: Use just two variables (min_price and max_profit) instead of storing all previous values - at each position, update min_price if current is lower, then check if selling now (current - min_price) beats max_profit, demonstrating how stateful iteration eliminates need for extra space.
• Zero-initialization edge case: Initialize max_profit to 0 rather than negative infinity - this naturally handles the case where no profitable transaction exists (all prices decreasing) without requiring special conditional logic, since any negative profit calculation won't update the result.
• Left-to-right dependency pattern: This problem exemplifies the prefix minimum pattern where each position only depends on aggregate information from all previous positions - recognize this in problems asking for "best outcome considering all prior elements" like max subarray, water trapping, or stock trading variants.
• Real-world streaming data application: This single-pass, constant-space approach is ideal for streaming scenarios where you process data once as it arrives (stock tickers, sensor readings, log analysis) and can't store or revisit all historical data, making it production-ready for memory-constrained or real-time systems.