Best Time to Buy and Sell Stock with Cooldown — Solution
Best Time to Buy and Sell Stock with Cooldown solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Best Time to Buy and Sell Stock with Cooldown is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array prices where prices[i] is the price of a stock on day i.
You may complete as many transactions as you like — buy one share and later sell it — with two restrictions: you may hold at most one share at a time, and after you sell you must wait one full day before buying again (a cooldown).
Return the maximum profit.
Example 1
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: buy, sell, cooldown, buy, sell.
Example 2
Input: prices = [1]
Output: 0
Example 3
Input: prices = [2,1]
Output: 0
Constraints
1 <= prices.length <= 400 <= prices[i] <= 1000
Hints for Best Time to Buy and Sell Stock with Cooldown
Hint 1
Each day you are in exactly one of three states: holding a share, having just sold, or resting with nothing.
Hint 2
holdcan come from staying held or from buying while resting;soldonly ever comes from selling what you held.Hint 3
restabsorbs the cooldown — it takes the previous day'ssold, which is what forbids buying the day after a sale.
How to solve Best Time to Buy and Sell Stock with Cooldown
Three states per day — hold (own a share), sold (sold today), rest (own nothing, free to buy) — with the cooldown enforced by feeding rest from the previous day's sold.
Approach
- Initialise
hold = -∞,sold = 0,rest = 0. - For each price:
sold = hold + price;hold = max(hold, rest - price);rest = max(rest, prevSold). - Return
max(sold, rest).
Why it works
Every day the trader is in exactly one state, and each transition is the best of its legal predecessors. Buying is only allowed from rest, and rest only absorbs sold one day later, which is precisely the one-day cooldown.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Save the previous
soldbefore overwriting it, or the cooldown silently disappears. - The answer is never
hold— ending with an unsold share is dominated.
Reference solution
Python
def maxProfit(prices) -> int:
hold = float("-inf")
sold = 0
rest = 0
for price in prices:
prev_sold = sold
sold = hold + price
hold = max(hold, rest - price)
rest = max(rest, prev_sold)
return max(sold, rest)Java
public static int maxProfit(int[] prices) {
final int NEG = -1000000;
int hold = NEG, sold = 0, rest = 0;
for (int price : prices) {
int prevSold = sold;
sold = hold + price;
hold = Math.max(hold, rest - price);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}C++
int maxProfit(vector<int>& prices) {
const int NEG = -1000000;
int hold = NEG, sold = 0, rest = 0;
for (int price : prices) {
int prevSold = sold;
sold = hold + price;
hold = max(hold, rest - price);
rest = max(rest, prevSold);
}
return max(sold, rest);
}JavaScript
var maxProfit = function(prices) {
let hold = -Infinity, sold = 0, rest = 0;
for (let i = 0; i < prices.length; i++) {
const prevSold = sold;
sold = hold + prices[i];
hold = Math.max(hold, rest - prices[i]);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming