Best Time to Buy and Sell Stock

LeetCode 121: Best Time to Buy and Sell Stock Solution & Explanation

Problem Overview

TL;DR: Iterate through the price array once while tracking the lowest price seen so far and calculating the maximum potential profit at each step.

The "Best Time to Buy and Sell Stock" problem asks us to determine the maximum profit achievable from a single transaction using a list of daily stock prices. A transaction consists of buying one stock on a specific day and selling it on a different, subsequent day. If no profit is possible (i.e., prices only decrease), the function should return 0.

This is a fundamental interview question, often referred to as LeetCode 121, and serves as the baseline for more complex dynamic programming problems involving state machines.

Brute Force Approach for Best Time to Buy and Sell Stock

The naive approach attempts to check every possible pair of buy and sell days to find the maximum difference. We can iterate through the array with a pointer i representing the buying day, and a nested pointer j (where j > i) representing the selling day.

Pseudo-code:

max_profit = 0
for i from 0 to length - 2:
    for j from i + 1 to length - 1:
        current_profit = prices[j] - prices[i]
        if current_profit > max_profit:
            max_profit = current_profit
return max_profit

Time Complexity: $O(N^2)$ The nested loops result in a quadratic number of comparisons. For an input size of $N = 10^5$, this results in approximately $10^{10}$ operations.

Why it fails: This approach fails due to Time Limit Exceeded (TLE) on large inputs. The constraints specify up to $100,000$ days, requiring an algorithm with linear $O(N)$ or log-linear $O(N \log N)$ complexity.

Algorithm Strategy: Dynamic Programming (DP) Patterns

We utilize a simplified Dynamic Programming approach where we optimize space complexity to $O(1)$. While standard DP might store a dp array, here we only need variables to track the current state.

1. Initialize States:

   • min_price: Initialize to a very large value (Infinity) to ensure the first price in the array updates it.
   • max_profit: Initialize to 0 (since negative profit is not allowed).

2. Iterate and Update:

   • Traverse the prices array from the first day to the last.
   • State Transition 1 (Update Minimum): If the current price is lower than min_price, update min_price. This implies we have found a better day to buy for any future transaction.
   • State Transition 2 (Update Profit): If the current price is not lower than min_price, calculate the difference (current_price - min_price). If this difference is greater than max_profit, update max_profit.

3. Return Result:

   • After the loop completes, max_profit holds the global maximum profit.

Execution Flow

Consider the input prices = [7, 1, 5, 3, 6, 4].

1. Initialization:

   • min_price = $\infty$
   • max_profit = 0

2. Iteration:

   • Day 0 (Price 7):
     • $7 < \infty$, so min_price becomes 7.
     • Profit calculation skipped (can't sell on buy day/price dropped).
   • Day 1 (Price 1):
     • $1 < 7$, so min_price becomes 1.
     • Price dropped, so we update our "buy" potential.
   • Day 2 (Price 5):
     • $5 > 1$. Potential profit = $5 - 1 = 4$.
     • max_profit becomes $\max(0, 4) = 4$.
   • Day 3 (Price 3):
     • $3 > 1$. Potential profit = $3 - 1 = 2$.
     • max_profit remains 4 ($4 > 2$).
   • Day 4 (Price 6):
     • $6 > 1$. Potential profit = $6 - 1 = 5$.
     • max_profit becomes $\max(4, 5) = 5$.
   • Day 5 (Price 4):
     • $4 > 1$. Potential profit = $4 - 1 = 3$.
     • max_profit remains 5.

3. Result: Return 5.

Proof of Correctness

The algorithm is correct because it exhaustively checks the optimal sell scenario for every single day. For any given day k acting as the sell day, the optimal buy day must be the day with the minimum price in the range 0 to k-1. By maintaining min_price as the running minimum, we guarantee that for every prices[i], we compute prices[i] - min(prices[0]...prices[i]). Since the global maximum profit must occur on some sell day, taking the maximum of all these local optimal choices yields the correct global maximum.

Pattern Reuse Notes

The logic used in "Best Time to Buy and Sell Stock" establishes the foundation for a series of related dynamic programming problems.

• LeetCode 122: Best Time to Buy and Sell Stock II: Allows unlimited transactions. The pattern shifts to summing all positive daily differences.
• LeetCode 123: Best Time to Buy and Sell Stock III: Limits to at most two transactions. The state expands to track buy1, sell1, buy2, sell2.
• LeetCode 188: Best Time to Buy and Sell Stock IV: Generalizes LeetCode 123 to k transactions using a DP array.
• LeetCode 309: Best Time to Buy and Sell Stock with Cooldown: Adds a state transition constraint where a "cooldown" state must follow a sell action.

Mastering the single-pass state tracking in LeetCode 121 is essential for understanding the multi-state DP transitions in these harder variants.

Reference Implementation

C++ Solution for LeetCode 121

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    int maxProfit(std::vector<int>& prices) {
8        int minPrice = INT_MAX;
9        int maxProfit = 0;
10
11        for (int price : prices) {
12            // Update the minimum price encountered so far
13            if (price < minPrice) {
14                minPrice = price;
15            } 
16            // Calculate potential profit if we sell at current price
17            else if (price - minPrice > maxProfit) {
18                maxProfit = price - minPrice;
19            }
20        }
21        
22        return maxProfit;
23    }
24};

Java Solution for LeetCode 121

1class Solution {
2    public int maxProfit(int[] prices) {
3        int minPrice = Integer.MAX_VALUE;
4        int maxProfit = 0;
5
6        for (int price : prices) {
7            // Update the minimum price encountered so far
8            if (price < minPrice) {
9                minPrice = price;
10            } 
11            // Calculate potential profit if we sell at current price
12            else if (price - minPrice > maxProfit) {
13                maxProfit = price - minPrice;
14            }
15        }
16        
17        return maxProfit;
18    }
19}

Python Solution for LeetCode 121

1class Solution:
2    def maxProfit(self, prices: list[int]) -> int:
3        min_price = float('inf')
4        max_profit = 0
5        
6        for price in prices:
7            # Update the minimum price encountered so far
8            if price < min_price:
9                min_price = price
10            # Calculate potential profit if we sell at current price
11            else:
12                current_profit = price - min_price
13                if current_profit > max_profit:
14                    max_profit = current_profit
15                    
16        return max_profit