Skip to main content

309. Best Time to Buy and Sell Stock with Cooldown

medium

Unlimited buy-sell pairs with a forced one-day cooldown after each sale. A textbook state-machine DP with three states: holding, sold, and resting.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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).

Constraints

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Each day you're in one of three states: holding a share, just sold (in cooldown), or idle (rested).

Hint 2

Transitions: hold -> sell or stay; sold -> must rest tomorrow; rest -> buy or stay rested.

Hint 3

Track three rolling values. The answer is max(sold, rest) on the last day.

Solution approach

Reveal approach

Model three states for each day: hold (currently own a share), sold (just sold today — must cooldown tomorrow), and rest (idle, can buy). Transitions: hold[i] = max(hold[i-1], rest[i-1] - prices[i]); sold[i] = hold[i-1] + prices[i]; rest[i] = max(rest[i-1], sold[i-1]). Initialize hold = -prices[0], sold = 0, rest = 0. Sweep through prices updating in the correct order using the previous values (or three temporaries). Answer is max(sold, rest) at the end. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Best Time to Buy and Sell Stock with Cooldown and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →