We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Best Time to Buy and Sell Stock with Cooldown

Number: 309

Difficulty: Medium

Paid? No

Companies: TikTok, Google, Amazon, Apple, Visa

Problem Description

Given an array prices where prices[i] is the price of a given stock on the ith day, determine the maximum profit achievable. You may execute as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the constraint that after you sell your stock, you cannot buy on the next day (i.e., a one-day cooldown). Note that you may not hold more than one stock at a time (i.e., you must sell a stock before you buy again).

Key Insights

  • Use Dynamic Programming to solve the problem.
  • Maintain three states to represent:
    • s0: the state where you are ready to buy (not holding any stock).
    • s1: the state where you are holding a stock.
    • s2: the cooldown state encountered right after selling a stock.
  • Transition between states:
    • Transition into s0 can come from staying in s0 or coming out from the cooldown state s2.
    • To enter s1, you either continue holding your stock, or buy a stock using the profit available from s0.
    • The only way to reach s2 is by selling the stock from s1.
  • The final answer is determined by the maximum profit when you are not holding a stock (i.e., max(s0, s2)).

Space and Time Complexity

Time Complexity: O(n), where n is the number of days. Space Complexity: O(1), since only a few variables are maintained for the states.

Solution

The solution involves updating three state variables for each day:

  1. s0 (ready to buy) is updated as the maximum of the previous s0 and the previous cooldown s2.
  2. s1 (holding a stock) is updated as the maximum of the previous s1 or buying today with the profit from s0 minus the current price.
  3. s2 (cooldown) is updated by selling the stock held in s1 (i.e., previous s1 plus the current price). At the end of the iteration, the maximum profit will be in state s0 (ready to buy) or s2 (cooldown), since remaining in s1 means you are holding a stock, which does not constitute a realized profit.

Code Solutions

# Python Solution with line-by-line comments

def maxProfit(prices):
    # Handle edge case: if there are no prices, profit is 0
    if not prices:
        return 0
    
    # Initialize states:
    # s0: Maximum profit when ready to buy
    # s1: Maximum profit when holding a stock (bought)
    # s2: Maximum profit during cooldown after a sale
    s0, s1, s2 = 0, -prices[0], 0
    
    # Iterate over prices starting from day 1
    for price in prices[1:]:
        # Store previous state values
        prev_s0, prev_s1, prev_s2 = s0, s1, s2
        # s0 can come either from staying in s0 or coming from a cooldown (s2)
        s0 = max(prev_s0, prev_s2)
        # s1 is updated by either keeping the stock or buying today with profit from s0
        s1 = max(prev_s1, prev_s0 - price)
        # s2 is achieved by selling the stock that we were holding (prev_s1 + price)
        s2 = prev_s1 + price
    # The final maximum profit is the maximum of not holding a stock (s0 or s2)
    return max(s0, s2)

# Example usage:
print(maxProfit([1,2,3,0,2]))
← Back to All Questions