Best Time to Buy and Sell Stock II
MedPrompt
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most efficient and intuitive approach. The key insight is that the total profit from a series of transactions is the sum of profits from individual, consecutive upward price movements. We can simply accumulate all positive gains from one day to the next.
Algorithm
- Initialize
maxProfit = 0. - Iterate through the
pricesarray from the second element (i = 1ton-1). - For each day
i, check if the price is higher than the previous day's price (prices[i] > prices[i-1]) - If it is, add the difference
prices[i] - prices[i-1]tomaxProfit. - After the loop finishes,
maxProfitwill hold the maximum possible profit.
Walkthrough
The problem allows us to buy and sell on the same day. This flexibility means we don't have to worry about finding the absolute lowest valley and highest peak over a long period. Instead, we can focus on short-term gains.
Consider a price sequence a, b, c. The profit from buying at a and selling at c is c - a. This is mathematically equivalent to (b - a) + (c - b). This implies that we can decompose a single large profitable transaction into a series of smaller, day-to-day profitable transactions.
Therefore, the strategy is to iterate through the prices and whenever we see an increase from day i-1 to day i (i.e., prices[i] > prices[i-1]), we "transact" and add the profit prices[i] - prices[i-1] to our total.
This is a greedy approach because at each step, we make the locally optimal choice of taking any available profit, and this leads to the globally optimal solution. This approach is also equivalent to a space-optimized version of the dynamic programming solution.
class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i-1]) { maxProfit += prices[i] - prices[i-1]; } } return maxProfit; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Highly efficient with linear time and constant space.
The logic is simple and easy to implement.
Cons
This specific greedy strategy works because of the problem's allowance for unlimited transactions. It might not be applicable to other stock problems with more constraints (e.g., transaction fees, cooldown periods).
This approach explores all possible transactions. For each day, we decide whether to buy, sell, or do nothing. This can be modeled using a recursive function that explores every possible sequence of actions.
Algorithm
- Define a recursive function
calculate(prices, index, holding). - Base Case: If
index >= prices.length, return 0. - If
holdingis true:sell_profit = prices[index] + calculate(prices, index + 1, false)hold_profit = calculate(prices, index + 1, true)- Return
max(sell_profit, hold_profit).
- If
holdingis false:buy_profit = -prices[index] + calculate(prices, index + 1, true)skip_profit = calculate(prices, index + 1, false)- Return
max(buy_profit, skip_profit).
- Start the process by calling
calculate(prices, 0, false).
Walkthrough
We define a recursive function, say calculate(index, holding), which calculates the maximum profit from a given index in the prices array, with a boolean holding indicating whether we currently own a stock.
Base Case: If index reaches the end of the array, no more transactions can be made, so the profit is 0.
Recursive Step:
- If we are
holdinga stock: We can either sell it today forprices[index]and recursively call for the next day withholding = false, or we can hold it and recursively call for the next day withholding = true. We take the maximum profit from these two choices. - If we are not
holdinga stock: We can either buy one today for-prices[index]and recursively call for the next day withholding = true, or we can skip buying and recursively call for the next day withholding = false. We take the maximum profit from these two choices.
The initial call to the function will be calculate(0, false). This method explores a binary decision tree, leading to an exponential number of calls.
class Solution { public int maxProfit(int[] prices) { return calculate(prices, 0, false); } private int calculate(int[] prices, int index, boolean holding) { if (index >= prices.length) { return 0; } // Option to do nothing and move to the next day int doNothingProfit = calculate(prices, index + 1, holding); int doSomethingProfit; if (holding) { // Option to sell doSomethingProfit = prices[index] + calculate(prices, index + 1, false); } else { // Option to buy doSomethingProfit = -prices[index] + calculate(prices, index + 1, true); } return Math.max(doNothingProfit, doSomethingProfit); }}Complexity
Time
O(2^n)
Space
O(n)
Trade-offs
Pros
Simple to conceptualize as it directly models the problem's decision process.
Cons
Extremely inefficient and will result in a "Time Limit Exceeded" error for larger inputs due to its exponential time complexity.
This approach improves upon the brute-force method by using tabulation to avoid recomputing results for the same subproblems. We can define the state by the current day and whether we are holding a stock.
Algorithm
- If
priceshas 0 or 1 element, return 0. - Create a DP table
dp[n][2]. - Initialize base cases:
dp[0][0] = 0anddp[0][1] = -prices[0]. - Iterate from
i = 1ton-1:dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
- Return
dp[n-1][0].
Walkthrough
We can solve this problem using a bottom-up dynamic programming approach. We'll create a 2D DP table, dp[n][2], where n is the number of days.
dp[i][0]will store the maximum profit achievable at the end of dayiif we are not holding any stock.dp[i][1]will store the maximum profit achievable at the end of dayiif we are holding one share of the stock.
State Transition Equations:
- To have no stock on day
i(dp[i][0]): We either had no stock on dayi-1and did nothing, or we held a stock on dayi-1and sold it on dayi.dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) - To hold a stock on day
i(dp[i][1]): We either held a stock on dayi-1and did nothing, or we had no stock on dayi-1and bought one on dayi.dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
Base Cases:
- On day 0, if we don't buy, the profit is 0:
dp[0][0] = 0. - On day 0, if we buy, the profit is
-prices[0]:dp[0][1] = -prices[0].
We iterate from day 1 to n-1, filling the DP table. The final answer is dp[n-1][0], as we must sell all stocks by the last day to maximize profit.
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) { return 0; } int n = prices.length; int[][] dp = new int[n][2]; // dp[i][0]: max profit on day i with no stock // dp[i][1]: max profit on day i with one stock // Base case dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; i++) { // Max profit with no stock today: // 1. Had no stock yesterday, do nothing. // 2. Had stock yesterday, sell it today. dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // Max profit with stock today: // 1. Had stock yesterday, do nothing. // 2. Had no stock yesterday, buy it today. dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[n-1][0]; }}Complexity
Time
O(n)
Space
O(n)
Trade-offs
Pros
Much more efficient than brute force.
Provides a structured way to solve the problem that can be adapted to more complex stock trading scenarios.
Cons
Uses extra space proportional to the input size.
Can be further optimized to use constant space.
Solutions
Solution
public class Solution { public int MaxProfit ( int [] prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . Length ; ++ i ) { ans += Math . Max ( 0 , prices [ i ] - prices [ i - 1 ]); } return ans ; } }class Solution { public int maxProfit ( int [] prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . length ; ++ i ) { ans += Math . max ( 0 , prices [ i ] - prices [ i - 1 ]); } return ans ; } }/** * @param {number[]} prices * @return {number} */ var maxProfit = function ( prices,) { let ans = 0; for (let i = 1; i < prices.length; i++) { ans += Math.max(0, prices[i] - prices[i - 1]); } return ans;};class Solution { public: int maxProfit ( vector < int >& prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . size (); ++ i ) ans += max ( 0 , prices [ i ] - prices [ i - 1 ]); return ans ; } };''' >>> from itertools import pairwise >>> dirs = (-1, 0, 1, 0, -1) >>> pairwise(dirs) <itertools.pairwise object at 0x104dbe470> >>> list(pairwise(dirs)) [(-1, 0), (0, 1), (1, 0), (0, -1)] ''' class Solution : def maxProfit ( self , prices : List [ int ]) -> int : return sum ( max ( 0 , b - a ) for a , b in pairwise ( prices )) class Solution : def maxProfit ( self , prices : List [ int ]) -> int : return sum ( max ( 0 , prices [ i ] - prices [ i - 1 ]) for i in range ( 1 , len ( prices )) ) class Solution : def maxProfit ( self , prices : List [ int ]) -> int : return sum ( prices [ i ] - prices [ i - 1 ] for i in range ( 1 , len ( prices )) if prices [ i ] > prices [ i - 1 ] ) ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ ans = 0 for i in range ( 1 , len ( prices )): if prices [ i ] > prices [ i - 1 ]: ans += prices [ i ] - prices [ i - 1 ] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.