Best Time to Buy and Sell Stock with Cooldown
Problem Description
Question
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]Output: 0
Constraints:
1 <= prices.length <= 50000 <= prices[i] <= 1000
Solve it on LeetCode
Approaches
1. Recursive Brute Force
Intuition:
- The idea here is to simulate each possible action (buy, sell, cooldown) at each day and keep track of the maximum profit.
- For each day, we can either:
- Not make any transaction (cooldown).
- Buy a stock (if currently not holding one).
- Sell a stock (only if currently holding a stock).
- We solve this using recursion by exploring each decision for each day and computing the maximum profit.
Code:
Complexity Analysis
- Time Complexity: O(2^n), where n is the number of days. We branch into two recursive calls for each day.
- Space Complexity: O(n), the stack space used for recursion.
2. Memoization
Intuition:
- The recursive solution computes the same subproblems multiple times, which increases time complexity.
- We can store the results of subproblems in a 2D array to avoid recalculating them, turning our approach into a dynamic programming solution.
Code:
Complexity Analysis
- Time Complexity: O(n), because each subproblem is solved at most once.
- Space Complexity: O(n), for the memo array.
3. Dynamic Programming
Intuition:
- Instead of recursion, we use dynamic programming arrays to keep track of the profits.
- We define two arrays:
sell[i]which is the maximum profit we can have up to dayi(inclusive) and must sell oni, andbuy[i]for transactions where max profit up toiand must buy oni.
Code:
Complexity Analysis
- Time Complexity: O(n), because we iterate over the prices once.
- Space Complexity: O(n), due to the
buyandsellarrays.
4. Space Optimized Dynamic Programming
Intuition:
- We can notice that to compute
buy[i]andsell[i], we only need the values fori-1andi-2. - Therefore, instead of maintaining arrays for
buyandsell, we maintain only variables for the last two and current states.
Code:
Complexity Analysis
- Time Complexity: O(n), since we iterate through the prices once.
- Space Complexity: O(1), as we are using a fixed number of variables instead of arrays.