LeetCode 121 - Best Time to Buy and Sell Stock

LeetCode Problem 121

Difficulty: 🟢 Easy
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to determine the maximum profit that can be made from a single stock transaction. A transaction consists of buying one stock on one day and selling it on a later day. The key restriction is that the selling day must come after the buying day.

The input is an integer array prices, where prices[i] represents the stock price on the i-th day. Since the array is ordered chronologically, the index itself implicitly represents time. Our goal is to find two days buy < sell such that the profit:

prices[sell] - prices[buy]

is maximized.

The expected output is the largest possible profit from one valid transaction. If no profitable transaction exists, meaning prices continuously decrease or stay the same, we return 0 because choosing not to trade is better than losing money.

The constraints provide important clues about the expected solution:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

The input size can be as large as 100,000, which immediately rules out slow quadratic approaches for production-quality solutions. Any algorithm worse than roughly O(n log n) risks timing out, and an O(n²) solution would be too slow for worst-case inputs.

Several edge cases are important to consider upfront:

• A single-element array, such as [5], where buying and selling are impossible because at least two days are required.
• Strictly decreasing prices, such as [7,6,4,3,1], where no profit can be made and the answer must be 0.
• Repeated values, such as [5,5,5,5], where profit is always zero.
• Cases where the minimum price appears early but the maximum selling opportunity occurs much later.
• Situations where the best selling day is not the global maximum price because buying constraints matter.

The problem guarantees that the array contains at least one price, so we never need to handle an empty input.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to try every possible buy and sell pair.

For each day i, we can consider it as the buying day and then iterate through every later day j > i to compute the profit:

prices[j] - prices[i]

We keep track of the maximum profit encountered across all valid pairs.

This approach is correct because it exhaustively checks every legal transaction and therefore cannot miss the optimal answer. However, it performs poorly because for every day we potentially compare against all later days.

If there are n days, we examine approximately:

n × (n - 1) / 2

pairs, resulting in O(n²) time complexity.

Given that n can be as large as 100,000, this approach becomes impractical.

Key Insight for the Optimal Solution

The crucial observation is that when deciding whether to sell on a given day, we only care about the lowest stock price seen before that day.

Instead of checking every earlier buying day repeatedly, we can maintain:

1. The minimum price encountered so far, representing the best buying opportunity.
2. The maximum profit found so far.

As we scan through the array from left to right:

• If the current price is lower than our recorded minimum, we update the minimum price.
• Otherwise, we calculate the profit if we sold today using the lowest price seen earlier.
• We update the best profit if this transaction is better.

This works because every day only depends on the cheapest valid buying price before it, which can be tracked incrementally in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible buy-sell pair
Optimal	O(n)	O(1)	Tracks minimum buying price while scanning once

Algorithm Walkthrough

1. Initialize a variable minimum_price with the first stock price. This represents the cheapest stock price we have seen so far and therefore the best buying opportunity available at the current point in time.
2. Initialize maximum_profit to 0. We begin with zero because making no transaction is always allowed, and profit can never be negative in the final answer.
3. Traverse the array starting from the second day. For each current price:

• First, compare it with minimum_price.
• If the current price is lower, update minimum_price because we have found a better buying opportunity.

4. If the current price is not lower, calculate the profit from selling today:

current_price - minimum_price

This represents the best possible profit if we sell on the current day. 5. Compare this profit with maximum_profit. If it is larger, update maximum_profit. 6. Continue until all days have been processed. 7. Return maximum_profit.

Why it works

The algorithm maintains an important invariant: at every index i, minimum_price stores the lowest stock price from all previous days 0..i-1.

Therefore, when evaluating selling on day i, we immediately know the best possible buying day that could precede it. Since every valid selling day is considered exactly once, and we always compare against the cheapest earlier price, the algorithm is guaranteed to find the globally optimal profit.

Python Solution

from typing import List

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

        for current_price in prices[1:]:
            if current_price < minimum_price:
                minimum_price = current_price
            else:
                current_profit = current_price - minimum_price
                maximum_profit = max(maximum_profit, current_profit)

        return maximum_profit

The implementation begins by storing the first stock price as minimum_price, since this is initially the only possible buying option.

The variable maximum_profit starts at 0, ensuring we correctly handle cases where no profitable transaction exists.

We then iterate through the remaining prices. If we encounter a cheaper stock price, we update minimum_price, because future selling days should use the best available purchase cost.

If the current price is greater than or equal to the minimum price, we calculate the potential profit from selling today. We compare this with the best profit found so far and update maximum_profit if necessary.

Finally, after processing all prices, we return the maximum profit discovered.

Go Solution

func maxProfit(prices []int) int {
	minimumPrice := prices[0]
	maximumProfit := 0

	for i := 1; i < len(prices); i++ {
		currentPrice := prices[i]

		if currentPrice < minimumPrice {
			minimumPrice = currentPrice
		} else {
			currentProfit := currentPrice - minimumPrice
			if currentProfit > maximumProfit {
				maximumProfit = currentProfit
			}
		}
	}

	return maximumProfit
}

The Go implementation follows the exact same logic as the Python version but uses Go idioms.

Since the constraints guarantee at least one element, accessing prices[0] is always safe. Go slices are used directly, and there is no distinction between nil and empty slices that matters here because LeetCode guarantees valid input.

Integer overflow is not a concern because stock prices are bounded by 10^4, making the profit safely fit within Go's int type.

Worked Examples

Example 1

Input:

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

We process the array from left to right.

Day	Price	Minimum Price So Far	Current Profit	Maximum Profit
0	7	7	-	0
1	1	1	-	0
2	5	1	4	4
3	3	1	2	4
4	6	1	5	5
5	4	1	3	5

The best transaction is:

Buy at 1
Sell at 6
Profit = 5

Output:

5

Example 2

Input:

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

Day	Price	Minimum Price So Far	Current Profit	Maximum Profit
0	7	7	-	0
1	6	6	-	0
2	4	4	-	0
3	3	3	-	0
4	1	1	-	0

The price keeps decreasing, so there is never a profitable selling opportunity.

Output:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array exactly once
Space	O(1)	Only a few variables are used regardless of input size

The time complexity is O(n) because each stock price is visited exactly once during the traversal. Every operation inside the loop runs in constant time.

The space complexity is O(1) because the algorithm only stores a few integer variables, independent of the size of the input array.

Test Cases

solution = Solution()

assert solution.maxProfit([7, 1, 5, 3, 6, 4]) == 5  # Provided example with profit
assert solution.maxProfit([7, 6, 4, 3, 1]) == 0  # Provided example, no profit

assert solution.maxProfit([5]) == 0  # Single element, cannot sell
assert solution.maxProfit([1, 2]) == 1  # Smallest profitable case
assert solution.maxProfit([2, 1]) == 0  # Smallest unprofitable case

assert solution.maxProfit([1, 2, 3, 4, 5]) == 4  # Strictly increasing prices
assert solution.maxProfit([5, 4, 3, 2, 1]) == 0  # Strictly decreasing prices
assert solution.maxProfit([5, 5, 5, 5]) == 0  # Constant prices

assert solution.maxProfit([3, 2, 6, 5, 0, 3]) == 4  # Best buy occurs before large rise
assert solution.maxProfit([2, 4, 1]) == 2  # Profit before later price drop
assert solution.maxProfit([1, 10, 2, 12]) == 11  # Better sell appears later
assert solution.maxProfit([10, 1, 10]) == 9  # Minimum appears after high price

Test	Why
[7,1,5,3,6,4]	Validates standard profitable scenario
[7,6,4,3,1]	Validates no-profit case
[5]	Ensures single-element input works
[1,2]	Smallest profitable input
[2,1]	Smallest unprofitable input
[1,2,3,4,5]	Tests continuously increasing prices
[5,4,3,2,1]	Tests continuously decreasing prices
[5,5,5,5]	Validates repeated equal values
[3,2,6,5,0,3]	Tests changing minimum price during traversal
[2,4,1]	Ensures early profit is preserved
[1,10,2,12]	Tests later higher profit
[10,1,10]	Validates minimum price discovered later

Edge Cases

A single-element array is an important edge case because no valid transaction can occur. You cannot both buy and sell with only one day available. A naive implementation might accidentally access an invalid index or assume at least two prices exist. Our implementation handles this naturally because the loop over prices[1:] becomes empty, leaving maximum_profit as 0.

A strictly decreasing price sequence, such as [7,6,4,3,1], can easily introduce bugs if an algorithm assumes profit must exist. In this situation, every later price is lower than the previous one, meaning every transaction would lose money. Our implementation correctly returns 0 because maximum_profit is initialized to zero and only updated when a positive profit appears.

A new minimum appearing late in the array, such as [10,1,10], is another subtle case. A naive solution might incorrectly anchor to the first value and miss a better buying opportunity later. Our algorithm continually updates minimum_price, ensuring that newly discovered cheaper prices are considered for all future transactions.

Another important edge case is repeated prices, such as [5,5,5,5]. Since selling never yields positive profit, the answer should remain 0. The implementation correctly handles equal prices because profit calculations never exceed zero.