Skip to content

121. Best Time to Buy and Sell Stock

On LeetCode ->

Problem

Given a list of daily stock prices, pick one day to buy and a later day to sell exactly once.

Return the maximum profit, or 0 if no profitable trade exists.

Example:

prices = [7, 1, 5, 3, 6, 4] -> 5
buy at 1, sell later at 6

Key trick

Scan once while keeping:

  • the lowest price seen so far
  • the best profit seen so far

For each price p, the best sell today is: p - min_price_so_far

Trap

Common mistakes:

  • forgetting sell must be after buy
  • trying all pairs, which is \(O(n^2)\)
  • tracking local rises instead of global best after the minimum so far
  • overcomplicating with multiple transactions, while this problem allows only one

Why is it interesting?

It looks like DP, but the clean solution is just one pass with two variables.

It tests whether you can turn a pair-comparison problem into a running-state problem.

Python solution

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0] # Minimum buy price seen so far.
        best = 0 # Best profit seen so far.

        for price in prices[1:]:
            best = max(best, price - min_price) # today
            min_price = min(min_price, price)

        return best

Comment on my solution

Your solution is much more complex than needed.

Problems:

  • global_max is unused for the final logic.
  • this condition is duplicated and likely a bug:
if p < global_min:
  • transactions models multiple candidate trades, but the problem only needs one running minimum and one running best profit
  • using dictionaries and a list adds unnecessary space and complexity
  • max([ ... ]) builds a list; if kept, max(...) with a generator would be better
  • the intended solution is \(O(n)\) time and \(O(1)\) space, while yours is \(O(n)\) extra space

A minimal fix is to replace the whole approach with the standard one-pass scan.

import pytest

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        p = prices[0]
        global_max = p
        global_min = p
        transactions = [{"min": p, "max": p}]
        for p in prices[1:]:
            if p < global_min:
                global_min = p
                transactions.append({"min": p, "max": p})
            if p > global_max:
                global_max = p
                transactions = [{"min": global_min , "max": global_max}]
            last_transaction_max = transactions[-1]["max"]
            transactions[-1]["max"] = max(last_transaction_max, p)
        return max([t["max"] - t["min"] for t in transactions])

@pytest.mark.parametrize(
    ("prices", "profit"),
    [
        ([7, 1, 5, 3, 6, 4], 5), # (1, 6)
        ([1, 3, 5, 6, 7], 6),    # (1, 7)
        ([7,6,4,3,1], 0),
        ([10, 6, 12, 4, 2, 4, 7, 6, 10], 8), # (2, 10)
        ([10, 6, 12, 4, 2, 4, 7, 6, 10, 1, 13], 12), # (1, 13)
        ([10, 6, 12, 4, 2, 4, 5], 6) # (6, 12)
    ],
)
def test_max_profit(prices, profit):
    assert Solution().maxProfit(prices) == profit