Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 121. Best Time to Buy and Sell Stock

Given an array of daily stock prices, compute the maximum profit achievable from exactly one buy-before-sell transaction (i.e., the largest prices[j] - prices[i] with j > i), or return 0 if no positive profit exists.

Asked at:

DESCRIPTION

Input:

prices = [7, 1, 5, 3, 6, 4]

Output:

Explanation: Buy on day 1 (price = 1) and sell on day 4 (price = 6), profit = 6 - 1 = 5. Note that buying on day 0 (price = 7) and selling on day 1 (price = 1) would result in a loss of -6, which is not allowed.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
Must buy before selling (cannot sell on the same day or before buying)
Return 0 if no positive profit is possible

Understanding the Problem

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.

Brute Force Approach

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.

Visualization

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

Start brute force: check all buy-sell pairs

0 / 91

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We use nested loops to check all pairs of buy and sell days, resulting in quadratic time complexity. For an array of length n, we perform roughly n*(n-1)/2 comparisons.

Space Complexity: O(1) We only use a constant amount of extra space to store the maximum profit and loop variables, regardless of input size.

Building Intuition

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.

Common Mistakes

Forgetting to initialize maxProfit to 0 instead of a negative value - this ensures we return 0 when no positive profit exists

Updating minPrice after calculating profit instead of before - this would allow buying and selling on the same day, which violates the constraint

Trying to track both buy and sell indices explicitly - this adds unnecessary complexity when we only need to track the minimum price

Not handling the edge case of a single-element array or empty array - these should return 0 since no transaction is possible

Calculating profit as minPrice - prices[i] instead of prices[i] - minPrice - this would give negative values when prices increase

Optimal Solution

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.

Visualization

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

Start: Find maximum profit from one buy-sell transaction

0 / 20

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We iterate through the array exactly once, performing constant-time operations at each step. This gives us linear time complexity.

Space Complexity: O(1) We only need two variables (minPrice and maxProfit) to track our state, using constant extra space regardless of array size.

What We've Learned

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.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early December, 2025

Marvin

Mid-level

Late November, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 121. Best Time to Buy and Sell Stock

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact