Is Best Time to Buy and Sell Stock with Cooldown easy or hard?

The problem is rated Medium because the difficulty comes from modeling the cooldown constraint correctly. Once the three-state dynamic programming relationship is identified, the implementation becomes a straightforward linear scan.

Best Time to Buy and Sell Stock with Cooldown Python/Java solution

Python and Java implementations typically follow the same DP state-machine logic. Maintain three variables (hold, sold, rest) and update them for each price in the array. The algorithm runs in O(n) time and O(1) space regardless of the programming language.

How to solve Best Time to Buy and Sell Stock with Cooldown in O(n)?

Track three DP states while iterating through the prices: hold (profit while holding a stock), sold (profit after selling today), and rest (profit while not holding and not selling). Update them using transitions hold = max(hold, rest - price), sold = hold + price, and rest = max(rest, previousSold). This single pass guarantees O(n) time.

What is the best approach for Best Time to Buy and Sell Stock with Cooldown?

The most efficient approach is iterative Dynamic Programming using three states: hold, sold, and rest. Each state represents the maximum profit while holding a stock, after selling, or resting due to cooldown. The algorithm updates these states in a single pass through the prices array, achieving O(n) time and O(1) space.

Is Best Time to Buy and Sell Stock with Cooldown asked at Google/Amazon/Meta?

Stock trading dynamic programming problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as transaction fees, cooldown periods, or limited transactions test a candidate's ability to design DP state transitions.

What data structure is used in Best Time to Buy and Sell Stock with Cooldown?

The solution primarily uses dynamic programming variables rather than complex data structures. The input is an array of prices, and the optimal algorithm maintains a few variables representing DP states such as hold, sold, and rest while iterating through the array.

What is the time complexity of Best Time to Buy and Sell Stock with Cooldown?

The optimal dynamic programming solution runs in O(n) time where n is the number of days in the prices array. Each price is processed once while updating a constant number of DP states. Space complexity can be reduced to O(1) by storing only the previous state values.

Description Solution Video 15:13

309. Best Time to Buy and Sell Stock with Cooldown

Medium62.4% acceptance8 companies

You are given an array prices where prices[i] is the price of a given stock on the i^th 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 <= 5000
0 <= prices[i] <= 1000

Asked at 8 companies

Geico Aqr Capital Management Apple

Google Tiktok Bloomberg Amazon Microsoft

Topics

Array Dynamic Programming

15:13

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

309. Best Time to Buy and Sell Stock with Cooldown

Asked at 8 companies

Topics

Similar problems