Abstract / Summary

Find the maximum profit from buying and selling stock with a cooldown period between transactions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic stock-trading problem with a cooldown period after each sale. It uses dynamic programming to track three mutually exclusive states for each day: ready to buy, holding a stock, and in cooldown. By iterating through the price list once and updating these states, the algorithm computes the maximum achievable profit while respecting the cooldown constraint.

State Representation

The core of the solution is the dp array, which holds the best profit for each of the three states after processing the previous day. The initial values are set to zero for the ready state and a large negative sentinel (Nope) for the other two, indicating that those states are unattainable before any price is seen.

Nope = -9999999
dp = [0, Nope, Nope]   # [ready, have stock, cooldown]

The sentinel ensures that any transition that relies on an impossible prior state will be ignored because the maximum operation will never select the sentinel value.

Transition Logic

For each price p in the input list, a new array next is constructed to hold the updated state values. The transitions reflect the allowed actions:

• Staying ready or emerging from cooldown: the ready state can be reached either by remaining ready (dp[0]) or by completing a cooldown (dp[2]).
• Buying or holding a stock: buying is possible only from the ready state (dp[0] - p), while holding continues the previous holding profit (dp[1]).
• Selling and entering cooldown: a sale is allowed only if a stock was held (dp[1] != Nope), producing profit dp[1] + p and moving into the cooldown state.

for p in prices:
    next = [0, Nope, Nope]

    next[0] = max(dp[0], dp[2])               # ready or exit cooldown
    next[1] = max(dp[0] - p, dp[1])           # buy or keep holding
    if dp[1] != Nope:                         # sell and start cooldown
        next[2] = dp[1] + p

    dp = next

After processing all prices, the answer is the maximum profit among the ready and cooldown states, because ending while still holding a stock would not realize its value.

return max(0, dp[0], dp[2])

Edge Cases Handled

The algorithm gracefully handles an empty price list. Since the loop body never executes, dp remains [0, Nope, Nope], and the final max call returns 0, indicating no profit is possible.

When all prices are decreasing, buying would never be beneficial. The transition next[1] = max(dp[0] - p, dp[1]) ensures that the holding state never improves beyond the sentinel, and the final max still yields 0.

The sentinel value prevents illegal transitions, such as selling before any purchase. The condition if dp[1] != Nope guarantees that a cooldown profit is only recorded after a legitimate sale.

Performance Considerations

The solution uses a constant-size array for state tracking, which means memory usage does not grow with the input length. By reusing the next array each iteration and assigning it back to dp, the implementation avoids allocating additional structures beyond two three-element lists.

All operations inside the loop are simple arithmetic and max comparisons, leading to a tight inner loop that benefits from CPU caching. The single pass over the price list ensures that the algorithm runs in linear time relative to the number of days, with minimal overhead.

Imagine playing a game where you want to collect shiny trading cards using only your pocket money. You have a list of prices showing how much each card costs on different days. This code helps you figure out the best way to buy and sell these cards to get the most money back.

The computer keeps track of three different feelings in its pretend pocket. One feeling means you are ready to buy a new card. Another feeling means you are already holding a card in your hand. The last feeling means you just sold a card and need a short break before buying another, kind of like resting after a long day of playing.

As the code goes through the list of prices, it looks at each day to see if it should do something new. It checks if buying a card today is a good idea, if selling one you already have makes sense, or if it is better to just wait and do nothing. It compares what happened yesterday with what could happen today to make sure you end up with the biggest pile of coins possible. At the end of the journey through the days, the computer looks at all the scenarios to see which one leaves you with the biggest reward.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java						TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java				Go		TS
	LeetcodeHelp	C++		Python	Java
	MemoryLimitExceeded	C++		Python
	Progiez	C++		Python	Java
github	aylei					Rust
	BigEggStudy		C#
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis						JS
	FelixFan1122		C#
	fengvyi	C++
	fpdjsns	C++
	fsq			Python
	halfrost								Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	lzl124631x	C++
	MacJim	C++
	ruoru					Rust
	shreymehul		C#
	sonugiri1043	C++
	suxrobGM		C#
	varunu28				Java
	vli02									C
	vthwang				Java
	wisdompeak			Python
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	Python
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality