121. Best Time to Buy and Sell Stock

Reformulated question¶

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.

Compact 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 - \text{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 this question 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.

Solve the problem with idiomatic python¶

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

        # Best profit seen so far.
        best = 0

        for price in prices[1:]:
            # If we sell today, profit uses the cheapest earlier buy.
            best = max(best, price - min_price)

            # Update cheapest buy for future days.
            min_price = min(min_price, price)

        return best

There is no standard library function that solves this exact problem more directly with the same interview-friendly clarity.

Pytest test¶

import pytest

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

Comment 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

Code¶

import pytest


class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # Keep the cheapest price seen so far and the best profit.
        min_price = prices[0]
        best = 0

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

        return best


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


Solution().maxProfit([7, 1, 5, 3, 6, 4])   # 5
Solution().maxProfit([7, 6, 4, 3, 1])      # 0
Solution().maxProfit([10, 6, 12, 4, 2, 4, 7, 6, 10])  # 8