121. Best Time to Buy and Sell Stock

Finding the best time to trade a stock is a practical example of optimizing decisions over time using simple scanning logic. Even with just one buy and one sell allowed, choosing the right pair of days can be surprisingly tricky because prices fluctuate and the best opportunity isn’t always obvious at first glance. This problem highlights how tracking key information as you move through the list can replace slow, repetitive comparisons with an efficient one-pass strategy.

Problem statement

You’re given a list of daily stock prices, where prices[i] is the price on day i. Your task is to pick one day to buy and a later day to sell to achieve the maximum possible profit.

Constraints:

• 1 ≤ prices.length ≤ $10^5$
• 0 ≤ prices[i] ≤ $10^4$

Examples

Why brute force is impractical

A simple approach is to first try every valid buy–sell combination by picking a day i as the buying day, and for that day, try every later day j > i as the selling day. Then we compute the profit as prices[j] - prices[i] and track the maximum profit from all buy-sell combinations.

While this logic is easy to reason about, it quickly becomes impractical. For an array of n days:

• Day 0 compares with n – 1 future days.
• Day 1 compares with n – 2 future days.
• …
• Day n – 2 compares with just one future day.

In total, this results in roughly n(n−1)/2​ comparisons.

With up to 10⁵ days, that means billions of profit calculations, most of which repeat similar checks over overlapping ranges of days. This not only makes the solution too slow to run within time limits, but also wastes effort re-evaluating the same price differences again and again.

Optimized approach using Greedy Techniques

The greedy optimization comes from the insight that for any day you choose to sell, the best possible buy must be the cheapest (lowest) price that occurred before that day. So, as you scan from left to right, you only need to track:

• The minimum price so far, i.e., the cheapest buying opportunity seen up to today
• The best profit so far, i.e., the maximum profit achievable up to today

For each day, treat the current price as a potential selling price:

• Compute the profit if you sell today as current price − minimum price so far
• Update best profit if the current profit is larger
• Update minimum price so far if today’s price is lower

Solution steps

1. Initialize min_price to the first day’s price.
2. Initialize best_profit to 0.
3. For each subsequent price p in the input array:
   1. Compute the profit if selling today: p - min_price.
   2. Update best_profit if this current profit is larger.
   3. Update min_price if p is smaller than the current min_price.
4. Return best_profit.

Take a look at the illustration below to understand the solution more clearly.

1 / 8

Python Implementation

Let’s look at the code for the solution we just discussed.

def maxProfit(prices):
    # Track the lowest price seen so far (best day to buy up to the current day)
    min_price = prices[0]

    # Track the maximum profit found so far (best buy-sell transaction)
    best_profit = 0

    # Start from the second day since we can't sell before we buy
    for p in prices[1:]:
        # Treat today's price as a potential selling price.
        # Profit if we sell today = today's price - lowest earlier price.
        best_profit = max(best_profit, p - min_price)

        # If today's price is lower than any seen before,
        # update the lowest price (better buying opportunity).
        if p < min_price:
            min_price = p

    # Return the best profit (0 if no profitable transaction exists)
    return best_profit
        
def main():

    test_cases = [
        [7, 1, 5, 3, 6, 4],
        [7, 6, 4, 3, 1],
        [1, 2, 3, 4, 5],
        [3, 3, 5, 0, 0, 3, 1, 4],
        [2, 4, 1],
    ]

    for i, prices in enumerate(test_cases, start=1):
        result = maxProfit(prices)
        print(f"{i}.\t Input prices = {prices}")
        print("\t maxProfit = ", result)
        print("-"*70)

   
if __name__ == "__main__":
    main()

Time complexity

The solution runs in linear time because it scans the prices array once, doing constant work per day. If n is the number of days, the runtime grows proportionally with n.

Space complexity

The solution uses constant extra space. It only stores a few variables, regardless of how large prices is.

Edge cases

• Single day (no possible sell day)
  Example: prices = [5]
  The loop doesn’t run, and best_profit stays 0, which is correct.
• Always decreasing prices
  Example: prices = [7, 6, 4, 3, 1]
  Every computed profit is <= 0, so best_profit remains 0.
• Profit is made by buying at a later low point and then selling after the price rises.
  Example: prices = [5, 4, 3, 2, 10]
  min_price keeps updating until 2, then profit becomes 10 – 2 = 8.
• Multiple equal minima
  Example: prices = [3, 1, 1, 2]
  min_price becomes 1 and stays there, allowing the correct profit 2 – 1 = 1.

Common pitfalls

• Trying to “buy and sell on the same day”
  The problem requires the sell day to be in the future. A correct scan only considers profits using a minimum from earlier days.
• Updating min_price before computing today’s profit
  If you update min_price first, you might accidentally allow buying today and selling today, which can hide bugs in some implementations.
• Returning negative profit
  The best answer must be 0 if no profit is possible. Initialize best_profit to 0, not to a negative number.
• Overcomplicating with multiple transactions logic
  This problem is strictly one transaction. Strategies that track multiple buy/sell segments are solving a different problem.