LeetCode 121: Best Time to Buy and Sell Stock

Problem Restatement

We are given an array prices, where prices[i] is the stock price on day i.

We may choose one day to buy one stock and a later day to sell it. We need to return the maximum possible profit. If no profit is possible, return 0. The official problem requires the selling day to be in the future after the buying day.

For example:

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

The best choice is:

buy at 1
sell at 6

The profit is:

6 - 1 = 5

So the answer is:

5

Input and Output

The function shape is:

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        ...

Examples

For:

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

Possible profitable choices include:

buy at 1, sell at 5 -> profit 4
buy at 1, sell at 3 -> profit 2
buy at 1, sell at 6 -> profit 5
buy at 3, sell at 6 -> profit 3

The best profit is:

5

For:

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

The price only decreases.

There is no future day where selling gives a positive profit, so the answer is:

0

First Thought: Try Every Buy and Sell Day

The direct approach is to test every pair of days.

Choose a buy day i.

Choose a sell day j, where:

j > i

Compute:

prices[j] - prices[i]

Track the maximum profit.

This works, but it checks too many pairs.

For n prices, this takes:

O(n^2)

We can do better.

Key Insight

When we are at a possible selling day, the best buying day is the lowest price seen before today.

So while scanning from left to right, keep:

For each price:

1. Treat it as the selling price.
2. Compute profit using the lowest earlier price.
3. Update the best profit.
4. Update the lowest price.

This respects the rule that we must buy before selling, because min_price only comes from days already scanned.

Algorithm

Initialize:

min_price = prices[0]
best = 0

Then scan every price:

1. Compute the profit if we sell today:

price - min_price

2. Update the best profit.
3. Update min_price if today’s price is lower.

Return best.

Correctness

At each day, min_price stores the smallest stock price from all previous days and the current day.

If we sell on the current day, the best possible buying price is the smallest price seen before or on this day. Buying on the same day gives profit 0, so it does not create an invalid positive profit.

The algorithm computes the best profit for each possible selling day using the best available earlier buying price. It then keeps the maximum among all such profits.

If prices always decrease, every computed profit is at most 0, and best remains 0.

Therefore, the algorithm returns the maximum profit possible from one valid transaction.

Complexity

Implementation

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        best = 0

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

        return best

Code Explanation

Start with the first price as the lowest price seen:

min_price = prices[0]

No transaction has been made yet, so best profit starts at 0:

best = 0

For each price, compute the profit if we sell today:

best = max(best, price - min_price)

Then update the minimum price:

min_price = min(min_price, price)

Finally:

return best

Testing

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]
        best = 0

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

        return best

def run_tests():
    s = Solution()

    assert s.maxProfit([7, 1, 5, 3, 6, 4]) == 5

    assert s.maxProfit([7, 6, 4, 3, 1]) == 0

    assert s.maxProfit([1, 2]) == 1

    assert s.maxProfit([2, 1, 2, 0, 1]) == 1

    assert s.maxProfit([3, 3, 3]) == 0

    print("all tests passed")

run_tests()

Test meaning: