Leetcode 309: Best Time to Buy and Sell Stock with Cooldown
grid47 Exploring patterns and algorithms
Oct 7, 2024
7 min read
Solution to LeetCode 309: Best Time to Buy and Sell Stock with Cooldown Problem
You are given an integer array ‘prices’, where ‘prices[i]’ represents the price of a stock on the i-th day. You are allowed to complete as many transactions as you like, with the restriction that after selling a stock, you cannot buy again the next day (cooldown). The goal is to calculate the maximum profit you can achieve by making any number of transactions while respecting the cooldown period.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array, 'prices', where each element represents the price of a stock on a specific day.
Example: prices = [1, 2, 3, 0, 2]
Constraints:
• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000
Output: The output is the maximum profit achievable by making transactions while respecting the cooldown period.
Example: For prices = [1, 2, 3, 0, 2], the output is 3.
Constraints:
Goal: To find the maximum profit achievable by completing multiple stock transactions while adhering to the cooldown constraint.
Steps:
• Use dynamic programming to track the states: whether we are holding a stock or not, and whether we're in a cooldown period.
• For each day, decide whether to buy, sell, or cooldown based on the previous decisions.
• Memoize the results to avoid redundant calculations and improve efficiency.
Goal: The solution needs to handle large inputs efficiently within the given constraints.
Steps:
• The array can have up to 5000 elements.
• The price of the stock can be between 0 and 1000.
Assumptions:
• The solution should handle edge cases like no profit or small arrays.
• Input: prices = [1, 2, 3, 0, 2]
• Explanation: The optimal transaction sequence is to buy on day 1 and sell on day 2, then cooldown on day 3, then buy on day 4 and sell on day 5. The total profit is 3.
• Input: prices = [5, 1, 3, 6, 4]
• Explanation: The optimal sequence is to buy on day 2, sell on day 3, buy on day 4, and sell on day 5. The total profit is 7.
• Input: prices = [1]
• Explanation: With only one price, no transaction is possible, and the maximum profit is 0.
Approach: A dynamic programming approach can be used to track different states of the stock transaction, such as holding a stock, not holding a stock, or being in a cooldown state.
Observations:
• We need to track whether we are holding a stock, not holding a stock, or in a cooldown state.
• We will use a 3D DP array to store the maximum profit for each state: holding a stock, not holding a stock, or in a cooldown state.
Steps:
• Define a 3D DP array to track states for each day.
• Iterate through the array and calculate the best decision at each point (buy, sell, or cooldown).
• Memoize intermediate results to avoid recomputing them.
Empty Inputs:
• If the array is empty, no transactions can be made, and the profit is 0.
Large Inputs:
• The solution must efficiently handle large arrays of up to 5000 elements.
Special Values:
• If all prices are the same, the maximum profit is 0 as no profit can be made.
Constraints:
• Ensure the solution runs within the time limits for large inputs.
Initializes a memoization table `memo` to store the results of subproblems. The table has dimensions `[5001][2][2]` to store results for each index, the buy status, and the cooldown status.
2 : Vector Declaration
vector<int> nums;
Declares a vector `nums` to store the stock prices for each day.
3 : Recursive Function Definition
intdp(int idx, bool buy, bool cool) {
Defines the recursive function `dp`, which computes the maximum profit for a given index `idx`, whether we can buy (`buy`), and whether we are in a cooldown period (`cool`).
4 : Base Case
if(idx == nums.size()) return0;
Base case: If the current index is equal to the size of the `nums` vector, return 0, meaning no more transactions are possible.
Checks the `memo` table to see if the result for the current state (`idx`, `buy`, `cool`) has already been computed. If so, return the stored result.
6 : Recursive Case 1 - No Transaction
int res = dp(idx +1, buy, false);
Recursively calls `dp` for the next index (`idx + 1`), with the same buy status and setting `cool` to `false` to simulate not making a transaction on the current day.
7 : Recursive Case 2 - Buy Stock
if(buy &&!cool) {
Checks if we are allowed to buy stock (`buy` is `true` and `cool` is `false`).
8 : Recursive Case 3 - Make Purchase
res = max(res, dp(idx +1, false, false) - nums[idx]);
If a purchase is made, recursively calls `dp` for the next day (`idx + 1`), setting `buy` to `false` and `cool` to `false`, while subtracting the current stock price from `res` (representing the cost of buying the stock).
9 : Recursive Case 4 - Sell Stock
} elseif(!buy) {
Checks if we are allowed to sell stock (`buy` is `false`).
10 : Recursive Case 5 - Make Sale
res = max(res, dp(idx +1, true, true) + nums[idx]);
If a sale is made, recursively calls `dp` for the next day (`idx + 1`), setting `buy` to `true` and `cool` to `true`, while adding the current stock price to `res` (representing the profit from selling the stock).
11 : Memoization Storage
return memo[idx][buy][cool] = res;
Stores the result of the current state (`idx`, `buy`, `cool`) in the `memo` table to avoid recalculating it in future calls.
12 : Main Function Definition
intmaxProfit(vector<int>& prices) {
Defines the `maxProfit` function, which computes the maximum profit that can be achieved given the array of stock prices `prices`.
13 : Memoization Initialization
memset(memo, -1, sizeof(memo));
Initializes the `memo` table to `-1` for all states, indicating that no subproblem has been solved yet.
14 : Store Prices
this->nums = prices;
Stores the input vector `prices` in the `nums` variable to be used in the `dp` function.
15 : Return Final Result
returndp(0, true, false);
Calls the `dp` function starting from index `0`, with the ability to buy stock and no cooldown period, and returns the result (maximum profit).
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only iterate through the array once, with each state transition taking constant time.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the DP array used to store the results for each day.
