Loading problems...
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.
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:
text
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_profitTime Complexity: The nested loops result in a quadratic number of comparisons. For an input size of , this results in approximately operations.
Why it fails: This approach fails due to Time Limit Exceeded (TLE) on large inputs. The constraints specify up to days, requiring an algorithm with linear or log-linear complexity.
The transition from the brute force approach to the optimal approach relies on a single observation: to maximize profit when selling on day i, we must have bought the stock at the absolute lowest price occurring before day i.
We do not need to compare day i with every single previous day. Instead, we only need to know the minimum price seen so far. This allows us to maintain a running state as we traverse the array.
Invariant:
At any index i, we maintain two values:
min_price: The lowest price encountered in prices[0...i].max_profit: The maximum profit achievable using any sell date up to i.Visual Description: Visualize the array of prices as a line graph where the x-axis represents days and the y-axis represents price. As we scan the graph from left to right, we maintain a "floor" line at the lowest y-value encountered. For every new point on the graph, we calculate the vertical distance between the current point and this floor. If the current point is below the floor, the floor updates to this new low. If the current point is above the floor, the vertical distance represents a potential profit. We record the largest vertical distance observed during the entire scan.
Consider the input prices = [7, 1, 5, 3, 6, 4].
Initialization:
min_price = max_profit = 0Iteration:
min_price becomes 7.min_price becomes 1.max_profit becomes .max_profit remains 4 ().max_profit becomes .max_profit remains 5.Result: Return 5.
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.
cpp#include <vector> #include <algorithm> #include <climits> class Solution { public: int maxProfit(std::vector<int>& prices) { int minPrice = INT_MAX; int maxProfit = 0; for (int price : prices) { // Update the minimum price encountered so far if (price < minPrice) { minPrice = price; } // Calculate potential profit if we sell at current price else if (price - minPrice > maxProfit) { maxProfit = price - minPrice; } } return maxProfit; } };
javaclass Solution { public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { // Update the minimum price encountered so far if (price < minPrice) { minPrice = price; } // Calculate potential profit if we sell at current price else if (price - minPrice > maxProfit) { maxProfit = price - minPrice; } } return maxProfit; } }
pythonclass Solution: def maxProfit(self, prices: list[int]) -> int: min_price = float('inf') max_profit = 0 for price in prices: # Update the minimum price encountered so far if price < min_price: min_price = price # Calculate potential profit if we sell at current price else: current_profit = price - min_price if current_profit > max_profit: max_profit = current_profit return max_profit
Time Complexity:
We perform a single pass through the prices array. Inside the loop, we perform constant-time operations (comparisons and arithmetic). Thus, the time complexity is linear with respect to the number of days.
Space Complexity:
We only use two variables (min_price and max_profit) to maintain the state, regardless of the input size.
The logic used in "Best Time to Buy and Sell Stock" establishes the foundation for a series of related dynamic programming problems.
buy1, sell1, buy2, sell2.k transactions using a DP array.Mastering the single-pass state tracking in LeetCode 121 is essential for understanding the multi-state DP transitions in these harder variants.
Q: Why does my solution get a Time Limit Exceeded (TLE)?
Q: Why is my output wrong when prices are descending (e.g., [7, 6, 4, 3, 1])?
max_profit to Integer.MIN_VALUE or a negative number, or failing to handle the case where no profit is possible.0.Q: Why can't I simply find the index of the minimum value and the index of the maximum value?
min(prices) and max(prices) independently and subtracting them.[5, 1]). You cannot sell before you buy.