Best Time to Buy and Sell Stock
Problem
Given an array prices where prices[i] is the price of a given stock on the ith day, return the maximum profit you can achieve by choosing a single day to buy one stock and a different day in the future to sell that stock.
- 1 ≤ prices.length ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁴
Example
prices = [7,1,5,3,6,4]5The algorithm starts with two pointers: l at index 0 (price 7) and r at index 1 (price 1). Since prices[l] (7) is not less than prices[r] (1), l moves to r (index 1). Then r advances to index 2 (price 5). Now prices[l] (1) < prices[r] (5), so profit is 4 and max_profit updates to 4. The process continues, updating max_profit to 5 when r reaches index 4 (price 6). The final max_profit is 5, achieved by buying at price 1 and selling at price 6.
Approach
Straightforward Solution
A brute-force approach checks every pair of days (buy and sell), resulting in O(n^2) time, which is too slow for large inputs.
Core Observation
The maximum profit is the largest difference between a later selling price and an earlier buying price. This requires tracking the minimum price seen so far and comparing it to future prices.
Path to Optimal
The key insight is to use two pointers: one tracking the minimum price (buy day) and the other scanning forward (sell day). If the current sell price is higher than the buy price, calculate profit and update max profit. If the sell price is lower or equal, move the buy pointer to the sell pointer, as this new price is a better candidate for buying. This approach reduces time complexity to O(n) by scanning the array once.
Optimal Approach
Use two pointers l and r initialized to 0 and 1. Iterate r through the array. If prices[l] < prices[r], update max_profit with prices[r] - prices[l]. Otherwise, move l to r. Increment r each iteration. Return max_profit after the loop completes.
Time
O(n)
The algorithm makes a single pass through the prices array with two pointers, each moving forward at most n times.
Space
O(1)
Only a fixed number of variables are used to track pointers and maximum profit, independent of input size.
Pattern Spotlight
Greedy Algorithms (Two Pointers for Optimal Substructure)
Track the lowest buying price seen so far and greedily update the maximum profit by comparing it with each future price; when a new lower price is found, reset the buying point to maintain the best potential profit.
Solution
| 1 | class Solution:
|
| 2 | def maxProfit(self, prices: list[int]) -> int:
|
| 3 | l, r = 0, 1
|
| 4 | max_profit = 0
|
| 5 |
|
| 6 | while r < len(prices):
|
| 7 | if prices[l] < prices[r]:
|
| 8 | profit = prices[r] - prices[l]
|
| 9 | max_profit = max(max_profit, profit)
|
| 10 | else:
|
| 11 | l = r
|
| 12 | r += 1
|
| 13 |
|
| 14 | return max_profit |
| 1 | class Solution { |
| 2 | public int maxProfit(int[] prices) { |
| 3 | int l = 0; |
| 4 | int r = 1; |
| 5 | int maxProfit = 0; |
| 6 | |
| 7 | while (r < prices.length) { |
| 8 | if (prices[l] < prices[r]) { |
| 9 | int profit = prices[r] - prices[l]; |
| 10 | maxProfit = Math.max(maxProfit, profit); |
| 11 | } else { |
| 12 | l = r; |
| 13 | } |
| 14 | r++; |
| 15 | } |
| 16 | |
| 17 | return maxProfit; |
| 18 | } |
| 19 | } |
Step-by-Step Solution
Initialize Two Pointers and Maximum Profit Tracker
| 3 | l, r = 0, 1
|
| 4 | max_profit = 0
|
Objective
To set up pointers for the buy day (l) and sell day (r), and initialize the maximum profit to zero.
Key Insight
Starting with l at 0 and r at 1 ensures the algorithm compares prices in chronological order, respecting the constraint that selling must occur after buying. Initializing max_profit to zero handles cases where no profit is possible.
Interview Quick-Check
Core Logic
Pointers l and r represent the buy and sell days respectively, maintaining the chronological order required for valid transactions.
State & Boundaries
Initialize max_profit to zero to correctly handle cases where prices never increase.
Iterate Through Prices to Update Profit and Buy Pointer
| 6 | while r < len(prices):
|
| 7 | if prices[l] < prices[r]:
|
| 8 | profit = prices[r] - prices[l]
|
| 9 | max_profit = max(max_profit, profit)
|
| 10 | else:
|
| 11 | l = r
|
| 12 | r += 1
|
Objective
To scan through the prices array, updating max_profit when a profitable sell is found, or moving the buy pointer when a lower price is encountered.
Key Insight
By comparing prices[l] and prices[r], the algorithm decides whether to calculate profit or update the buy pointer. This greedy decision ensures the buy pointer always points to the lowest price seen so far, maximizing potential profit.
Interview Quick-Check
Core Logic
If prices[r] > prices[l], calculate profit and update max_profit if it's higher; otherwise, move l to r to track a new minimum buying price.
State & Boundaries
The loop continues while r is within the array bounds, ensuring all potential sell days are considered.
Common Pitfalls & Bugs
Failing to move the buy pointer when a lower price is found leads to incorrect profit calculations and missed opportunities.
Return the Maximum Profit Found
| 14 | return max_profit |
Objective
To output the maximum profit calculated after scanning all prices.
Key Insight
Returning max_profit after the loop ensures the algorithm outputs the best possible profit or zero if no profitable transaction exists.
Interview Quick-Check
Core Logic
Return the maximum profit found, which represents the best buy-sell pair.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
max_profit = max(max_profit, profit)Update max_profit if the current profit is greater than the previous maximum.
This line is the critical step that maintains the global maximum profit by comparing the current profit to the best known, ensuring the algorithm returns the optimal solution.
l = rMove the buy pointer to the current sell pointer.
This line is crucial because it updates the buying day to the lowest price seen so far, enabling the greedy strategy to find the maximum profit by always buying at the lowest price before selling.
if prices[l] < prices[r]:Check if the current buy price is less than the current sell price.
This condition identifies profitable transactions, as selling at a higher price than buying yields positive profit.
return max_profitReturn the maximum profit found after scanning all prices.
Returning max_profit outputs the final answer, which is the best achievable profit or zero if no profitable transaction exists.
l, r = 0, 1Initialize left pointer to 0 (buy day) and right pointer to 1 (sell day).
Setting l and r this way ensures the algorithm respects the chronological order of buying before selling, which is essential for correctness.
profit = prices[r] - prices[l]Calculate the profit from buying at l and selling at r.
Computing this difference quantifies the gain from the current buy-sell pair, which is the core metric the algorithm seeks to maximize.
else:Else clause for when the current sell price is not greater than the buy price.
This branch handles the case where a new lower price is found, indicating a better buying opportunity.
max_profit = 0Initialize max_profit to zero.
Starting max_profit at zero correctly handles cases where no profitable transaction is possible, ensuring the function returns zero rather than a negative value.
while r < len(prices):Begin a loop that continues while the sell pointer is within the prices array.
This loop ensures every potential sell day after the buy day is considered exactly once, enabling a linear scan of the array.
r += 1Increment the sell pointer to consider the next day.
Advancing the sell pointer ensures the algorithm examines all possible sell days after the current buy day.
Test Your Understanding
Why does moving the buy pointer to the sell pointer when prices[r] <= prices[l] guarantee correctness?
Because a lower price at r offers a better buying opportunity, and any profit calculated using a higher buy price before r would be suboptimal; thus, resetting the buy pointer ensures the algorithm always considers the lowest possible buy price before selling.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Best Time to Buy and Sell Stock from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Best Time to Buy and Sell Stock drill