Best Time to Buy And Sell Stock With Cooldown
Best Time to Buy And Sell Stack With Cooldown
- This problem is a variation of the classic “Buy and Sell Stock” challenge, incorporating a cooldown period after selling.
- The goal is to maximize profit by strategically planning when to buy, sell, and stay idle.
Best Time to Buy And Sell Stock With Cooldown Problem Description:
You are given an array prices where prices[i] represents the price of a stock on day ii. You may complete as many transactions as you’d like (buy one stock and sell one stock), but with the following restrictions:
- After selling a stock, you must wait for one day before buying again (cooldown period).
- You may only hold one stock at any given time.
Return the maximum profit achievable.
Example 1:
Example 1
Input: prices = [1,3,4,0,4]
Output: 6
Explanation: Buy on day 0 (price = 1) and sell on day 1 (price = 3), profit = 3-1 = 2. Then buy on day 3 (price = 0) and sell on day 4 (price = 4), profit = 4-0 = 4. Total profit is 2 + 4 = 6.
Example 2
Input: prices = [1]
Output: 0
Constraints:
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
Best Time to Buy And Sell Stock With Cooldown Solution
Recommendation for Time and Space Complexity – The solution should aim for O(n!) time and O(n²) space, where n is the size of the chessboard.
Hints for solving problems
There are mainly 4 approach to solve this problem-
- Recursion
- Dynamic Programming (Top-Down)
- Dynamic Programming (Bottom-up)
- Dynamic Programming (Space Optimized)
1. Recursion
- Time complexity: O(n^2)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int maxProfit(vector& prices) {
return dfs(0, true, prices);
}
private:
int dfs(int i, bool buying, vector& prices) {
if (i >= prices.size()) {
return 0;
}
int cooldown = dfs(i + 1, buying, prices);
if (buying) {
int buy = dfs(i + 1, false, prices) - prices[i];
return max(buy, cooldown);
} else {
int sell = dfs(i + 2, true, prices) + prices[i];
return max(sell, cooldown);
}
}
};
Java
public class Solution {
public int maxProfit(int[] prices) {
return dfs(0, true, prices);
}
private int dfs(int i, boolean buying, int[] prices) {
if (i >= prices.length) {
return 0;
}
int cooldown = dfs(i + 1, buying, prices);
if (buying) {
int buy = dfs(i + 1, false, prices) - prices[i];
return Math.max(buy, cooldown);
} else {
int sell = dfs(i + 2, true, prices) + prices[i];
return Math.max(sell, cooldown);
}
}
}
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
def dfs(i, buying):
if i >= len(prices):
return 0
cooldown = dfs(i + 1, buying)
if buying:
buy = dfs(i + 1, not buying) - prices[i]
return max(buy, cooldown)
else:
sell = dfs(i + 2, not buying) + prices[i]
return max(sell, cooldown)
return dfs(0, True)
JavaScript
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
const dfs = (i, buying) => {
if (i >= prices.length) {
return 0;
}
let cooldown = dfs(i + 1, buying);
if (buying) {
let buy = dfs(i + 1, false) - prices[i];
return Math.max(buy, cooldown);
} else {
let sell = dfs(i + 2, true) + prices[i];
return Math.max(sell, cooldown);
}
}
return dfs(0, true);
}
}
2.Dynamic Programming (Top-Down)
- Time complexity: O(n)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
class Solution {
public:
unordered_map dp;
int maxProfit(vector& prices) {
return dfs(0, true, prices);
}
private:
int dfs(int i, bool buying, vector& prices) {
if (i >= prices.size()) {
return 0;
}
string key = to_string(i) + "-" + to_string(buying);
if (dp.find(key) != dp.end()) {
return dp[key];
}
int cooldown = dfs(i + 1, buying, prices);
if (buying) {
int buy = dfs(i + 1, false, prices) - prices[i];
dp[key] = max(buy, cooldown);
} else {
int sell = dfs(i + 2, true, prices) + prices[i];
dp[key] = max(sell, cooldown);
}
return dp[key];
}
};
Java
public class Solution {
private Map dp = new HashMap<>();
public int maxProfit(int[] prices) {
return dfs(0, true, prices);
}
private int dfs(int i, boolean buying, int[] prices) {
if (i >= prices.length) {
return 0;
}
String key = i + "-" + buying;
if (dp.containsKey(key)) {
return dp.get(key);
}
int cooldown = dfs(i + 1, buying, prices);
if (buying) {
int buy = dfs(i + 1, false, prices) - prices[i];
dp.put(key, Math.max(buy, cooldown));
} else {
int sell = dfs(i + 2, true, prices) + prices[i];
dp.put(key, Math.max(sell, cooldown));
}
return dp.get(key);
}
}
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = {} # key=(i, buying) val=max_profit
def dfs(i, buying):
if i >= len(prices):
return 0
if (i, buying) in dp:
return dp[(i, buying)]
cooldown = dfs(i + 1, buying)
if buying:
buy = dfs(i + 1, not buying) - prices[i]
dp[(i, buying)] = max(buy, cooldown)
else:
sell = dfs(i + 2, not buying) + prices[i]
dp[(i, buying)] = max(sell, cooldown)
return dp[(i, buying)]
return dfs(0, True)
JavaScript
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
const dp = {};
const dfs = (i, buying) => {
if (i >= prices.length) {
return 0;
}
let key = `${i}-${buying}`;
if (key in dp) {
return dp[key];
}
let cooldown = dfs(i + 1, buying);
if (buying) {
let buy = dfs(i + 1, false) - prices[i];
dp[key] = Math.max(buy, cooldown);
} else {
let sell = dfs(i + 2, true) + prices[i];
dp[key] = Math.max(sell, cooldown);
}
return dp[key];
}
return dfs(0, true);
}
}
3. Dynamic Programming (Bottom-Up)
- Time complexity: O(n)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
vector> dp(n + 1, vector(2, 0));
for (int i = n - 1; i >= 0; --i) {
for (int buying = 1; buying >= 0; --buying) {
if (buying == 1) {
int buy = dp[i + 1][0] - prices[i];
int cooldown = dp[i + 1][1];
dp[i][1] = max(buy, cooldown);
} else {
int sell = (i + 2 < n) ? dp[i + 2][1] + prices[i] : prices[i];
int cooldown = dp[i + 1][0];
dp[i][0] = max(sell, cooldown);
}
}
}
return dp[0][1];
}
};
Java
public class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n + 1][2];
for (int i = n - 1; i >= 0; i--) {
for (int buying = 1; buying >= 0; buying--) {
if (buying == 1) {
int buy = dp[i + 1][0] - prices[i];
int cooldown = dp[i + 1][1];
dp[i][1] = Math.max(buy, cooldown);
} else {
int sell = (i + 2 < n) ? dp[i + 2][1] + prices[i] : prices[i];
int cooldown = dp[i + 1][0];
dp[i][0] = Math.max(sell, cooldown);
}
}
}
return dp[0][1];
}
}
Python
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
vector> dp(n + 1, vector(2, 0));
for (int i = n - 1; i >= 0; --i) {
for (int buying = 1; buying >= 0; --buying) {
if (buying == 1) {
int buy = dp[i + 1][0] - prices[i];
int cooldown = dp[i + 1][1];
dp[i][1] = max(buy, cooldown);
} else {
int sell = (i + 2 < n) ? dp[i + 2][1] + prices[i] : prices[i];
int cooldown = dp[i + 1][0];
dp[i][0] = max(sell, cooldown);
}
}
}
return dp[0][1];
}
};
JavaScript
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
const n = prices.length;
const dp = Array.from({ length: n + 1 }, () => [0, 0]);
for (let i = n - 1; i >= 0; i--) {
for (let buying = 1; buying >= 0; buying--) {
if (buying === 1) {
let buy = dp[i + 1][0] - prices[i];
let cooldown = dp[i + 1][1];
dp[i][1] = Math.max(buy, cooldown);
} else {
let sell = (i + 2 < n) ? dp[i + 2][1] + prices[i] : prices[i];
let cooldown = dp[i + 1][0];
dp[i][0] = Math.max(sell, cooldown);
}
}
}
return dp[0][1];
}
}
4. Dynamic Programming (Space Optimized)
- Time complexity: O(n)
- Space complexity: O(1)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int col = 0, posDiag = 0, negDiag = 0;
vector<string> board;
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
board.resize(n, string(n, '.'));
backtrack(0, n);
return res;
}
void backtrack(int r, int n) {
if (r == n) {
res.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if ((col & (1 << c)) || (posDiag & (1 << (r + c)))
|| (negDiag & (1 << (r - c + n)))) {
continue;
}
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = 'Q';
backtrack(r + 1, n);
col ^= (1 << c);
posDiag ^= (1 << (r + c));
negDiag ^= (1 << (r - c + n));
board[r][c] = '.';
}
}
};
Java
public class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp1_buy = 0, dp1_sell = 0;
int dp2_buy = 0;
for (int i = n - 1; i >= 0; i--) {
int dp_buy = Math.max(dp1_sell - prices[i], dp1_buy);
int dp_sell = Math.max(dp2_buy + prices[i], dp1_sell);
dp2_buy = dp1_buy;
dp1_buy = dp_buy;
dp1_sell = dp_sell;
}
return dp1_buy;
}
}
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp1_buy, dp1_sell = 0, 0
dp2_buy = 0
for i in range(n - 1, -1, -1):
dp_buy = max(dp1_sell - prices[i], dp1_buy)
dp_sell = max(dp2_buy + prices[i], dp1_sell)
dp2_buy = dp1_buy
dp1_buy, dp1_sell = dp_buy, dp_sell
return dp1_buy
JavaScript
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
const n = prices.length;
let dp1_buy = 0, dp1_sell = 0;
let dp2_buy = 0;
for (let i = n - 1; i >= 0; i--) {
let dp_buy = Math.max(dp1_sell - prices[i], dp1_buy);
let dp_sell = Math.max(dp2_buy + prices[i], dp1_sell);
dp2_buy = dp1_buy;
dp1_buy = dp_buy;
dp1_sell = dp_sell;
}
return dp1_buy;
}
}
