LeetCode 121 - Best Time to Buy and Sell Stock

This Easy problem asks for the maximum profit from buying once and selling once. For each day, I treated the current price as the selling price and compared it with the lowest price seen earlier.

Problem link and explanation

Problem: 121. Best Time to Buy and Sell Stock
Summary: Each value in prices is a stock price on a particular day. Return the maximum profit from buying on one day and selling on a later day. Return 0 if no profitable transaction exists.

For [7, 1, 5, 3, 6, 4], buying at 1 and selling at 6 produces the maximum profit of 5. The buy must occur before the sale.

Approach

If the current day is the selling day, the best possible purchase price is the lowest price from the days already examined. A single left-to-right pass therefore needs only two values.

min_price is the lowest price encountered so far.
max_profit is the largest profit calculated so far.

Subtracting min_price from the current price gives the profit from selling today. I compare it with max_profit, then update min_price if the current price is lower.

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

For [7, 1, 5, 3, 6, 4], min_price starts at 7 and changes to 1 on the second value. The scan then calculates profits of 4 at price 5, 2 at price 3, and 5 at price 6, leaving max_profit at 5.

Troubleshooting

My first idea was to pair every price with its original index, sort those tuples by price, and place two pointers at the cheapest and most expensive values. I planned to move inward from both ends and accept a profit when the buy index was smaller than the sell index.

The problem was deciding which pointer to move when the index order was invalid. Consider [3, 2, 6, 1, 4]. Sorting (price, index) pairs produces:

[(1, 3), (2, 1), (3, 0), (4, 4), (6, 2)]

The outer prices, 1 and 6, cannot form a transaction because the buy index 3 comes after the sell index 2. Moving the right pointer finds a profit of 3 by buying at 1 and selling at 4, but the actual maximum is 4 from buying at 2 at index 1 and selling at 6 at index 2. This example requires moving the left pointer, while another input may require moving the right one.

Price order alone does not provide a rule proving that discarding either side preserves the optimal answer. Exploring both choices would bring back a larger combination search, and sorting already costs O(n log n), so I did not use this approach.

A left-to-right pass preserves the time constraint directly. The code calculates profit using the current min_price before updating it, so a newly discovered minimum becomes a candidate purchase price only for later days. On the first iteration, the first price is compared with itself and produces a profit of 0.

Starting max_profit at 0 also handles a continuously falling market. Every possible transaction has a non-positive profit, so the method returns the profit from making no transaction.

Complexity analysis

Time complexity: O(n)
- The algorithm scans prices once from left to right.
Space complexity: O(1)
- It stores only min_price and max_profit, regardless of input size.

Implementation code

from typing import List

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

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

        return max_profit

Summary and reflection

For any selling day, the only historical value needed is the lowest earlier price. Checking every buy-and-sell pair would take O(n²) time, while retaining the previous minimum reduces the same decision to O(n).

Unlike finding the global minimum and maximum independently, the left-to-right scan also preserves the requirement that buying must happen before selling. Keeping only the state needed for the next price holds the extra space to O(1).