How do you solve Best Time to Buy and Sell Stock with Cooldown on LeetCode?

Best Time to Buy and Sell Stock with Cooldown (LeetCode #309) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding the cooldown period is crucial for making optimal decisions.

What is the brute force solution for Best Time to Buy and Sell Stock with Cooldown?

The brute force approach for Best Time to Buy and Sell Stock with Cooldown is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves trying every possible transaction combination to find the maximum profit. This means checking every day to see if buying and selling on that day yields a better profit, considering the cooldown period. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Best Time to Buy and Sell Stock with Cooldown?

Best Time to Buy and Sell Stock with Cooldown uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Array.

What are the interview tips for Best Time to Buy and Sell Stock with Cooldown?

Clearly explain your thought process as you work through the problem. Consider edge cases, such as an empty prices array or prices that only decrease. Practice breaking down the problem into smaller parts to make it more manageable.

What are common mistakes when solving Best Time to Buy and Sell Stock with Cooldown?

Not considering the cooldown day when deciding to buy or sell. Overcomplicating the problem by trying to track too many states.

#309

Best Time to Buy and Sell Stock with Cooldown

Medium

ArrayDynamic ProgrammingDynamic ProgrammingArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Using dynamic programming, we can keep track of the maximum profit at each day while considering the cooldown period. This allows us to efficiently calculate the maximum profit without redundant calculations.

⚙️

Algorithm

3 steps

1Step 1: Create three variables to track the maximum profit on the previous day with no stock, with stock, and the cooldown.
2Step 2: Iterate through the prices array and update these variables based on the current price and the previous states.
3Step 3: At the end, the maximum profit will be in the no stock variable.

solution.py9 lines

1def maxProfit(prices):
2    if not prices: return 0
3    sold, held, reset = 0, float('-inf'), 0
4    for price in prices:
5        prev_sold = sold
6        sold = held + price
7        held = max(held, reset - price)
8        reset = max(reset, prev_sold)
9    return sold

ℹ

Complexity note: The time complexity is O(n) because we only pass through the prices array once. The space complexity is O(1) since we only use a fixed amount of extra space.

1Understanding the cooldown period is crucial for making optimal decisions.
2Dynamic programming allows us to build on previous results rather than recalculating.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.