Best Time to Buy and Sell Stock with Cooldown - Leetcode 309 - Python

[@DennisSmdFreefightTrainer]

thats literally a template for almost all of the "Buy and Sell Stock" Problems on Leetcode. So much more easy to understand and come up with during an interview then the state-machine approach. Thank you Sir!

[@uniquename2386]

Yeah, with this approach you can solve 714. Best Time to Buy and Sell Stock with Transaction Fee.

[@jamesbotwina8744]

I think it would be helpful if you think of the buying state as "looking to buy" state. When it is negative, it means that we have already bought or are calculating what happens if we wait. After we sell, we want to "look to buy" two indexes in the future.

[@kurtkuhn4045]

The gods have listened! I was looking your solution to this problem and you helped incredibly. Thank you! The answers posted on LC aren’t very well explained to poor wording

[@eggfryrice308]

Thank you so much, I think you are the best on youtube explaining these. I especially like the fact that you explain the solution without the code first. For this problem I think calling the parameter "buying" is not exact, it's more like "canbuy" in my understanding.

[@NeetCode]

That's a good point, I think "canbuy" is definitely a better name for it.

[@josephmasinre1840]

you can make it a bit faster if you consider the fact that you should only buy at local mins, but the overall time complexity is still the same. def maxProfit(self, prices: List[int]) -> int: DP = {} def stock(i, buy): if i >= len(prices): return 0 if (i, buy) in DP: return DP[(i, buy)] if buy: j = i while j < len(prices)-1 and prices[j] > prices[j+1]: #look for local min j += 1 b = stock(j+1, not buy) - prices[j] #buy at local min c = stock(j+1, buy) DP[(i, buy)] = max(b, c) else: s = stock(i+2, not buy) + prices[i] c = stock(i+1, buy) DP[(i, buy)] = max(s, c) return DP[(i, buy)] return stock(0, True)

[@sithlord3442]

Thank you so much. I was struggling with this problem earlier in the day! Love your explanations

[@yunaf4609]

Great explanation. The verbosity of the problem is intimidating but your explanation makes it much simpler, it makes sense as a DP problem. Amazing job as always :)

[@RolopIsHere]

sold, held, reset = float('-inf'), float('-inf'), 0 for price in prices: pre_sold = sold sold = held + price held = max(held, reset - price) reset = max(reset, pre_sold) return max(sold, reset)

[@shrimpo6416]

I struggled with this one a whole afternoon and your video just saved my day!

[@rahulsbhatt]

I'm amazed by the neetness of your code and clarity for this problem!

[@tanson86]

@Neetcode, Thanks for the simple explanation. Pasting the exact solution in java, just in case someone is looking for it. public int maxProfit(int[] prices) { return maxProfit(prices,0,true,new HashMap()); } public int maxProfit(int[] prices,int i,boolean buying,Map map){ if(i>=prices.length) return 0; if(map.containsKey(i+"-"+buying)) return map.get(i+"-"+buying); if(buying){ int buy = maxProfit(prices,i+1,!buying,map)-prices[i]; int cd = maxProfit(prices,i+1,buying,map); map.put(i+"-"+buying, Math.max(buy,cd)); }else{ int sell = maxProfit(prices,i+2,!buying,map)+prices[i]; int cd = maxProfit(prices,i+1,buying,map); map.put(i+"-"+buying, Math.max(sell,cd)); } return map.get(i+"-"+buying); }

[@JunjieYu-y2b]

I love the idea of deducting the price from profit when you buy the stock, simple trick but make it a lot easier

[@venkatrampramod7978]

A great explanation again. My dilemma is if one hasn't seen the solution before or solved it on one's own, it would really, really hard to come up with a solution in an actual interview of 45 minutes (unless one is brilliant like you!) The other thing is one rarely needs to solve such a problem in real life. The problems that are encountered are more mundane and easy to resolve. If one does encounter such a problem, one would definitely have more than 45 minutes to solve (perhaps several days)

[@Qwantopides]

I had the same mindset as you for these types of problems in general. What I have realized however that this approach is simply incorrect. Whether or not you may or may not encounter such or similar problems in the wild doesn't matter at all. Your ability to solve novel problems with time or other constraints does. And this skill can only be trained by problem solving. Think of your brains ability to solve random problems as a muscle. Keeping with the analogy, to have a good performing brain, you have to train it in ways it isn't used to.

[@bhoomeendra]

@@Qwantopides These are fairly standard problems after doing around 10-15 dp problem you would see the same patterns

[@brokecoder]

Your lazy ass, looking for excuse not to do the problems

[@dryng6006]

Is there a way to do this bottom-up? When you're solving these problems how do you decide whether to just implement top-down (after figuring out brute force) or continue and try to implement bottom-up? Thanks so much!

[@roshansaundankar4893]

This is bottom up he returns a zero and then keeps adding as he keeps going up the recursion tree.

[@kaelanm-s3919]

buy_prof, sell_prof, sell_prof2 = -1e5, 0, 0 for p in prices: buy_prof = max(buy_prof, sell_prof2-p) sell_prof2 = sell_prof sell_prof = max(sell_prof, buy_prof+p) return sell_prof beats 99.8% buy_prof = maximum profit if last or current action is buying sell_prof = maximum profit if last or current action is selling sell_prof2 = previous sell_prof

[@schan263]

@@roshansaundankar4893 No, this is top-down DP. Bottom-up DP doesn't use recursion.

[@wij8044]

Hash for cache -> top down

[@justine-george]

dp = [[0] * 2 for _ in range(len(prices) + 2)] for cur in range(len(prices) - 1, -1, -1): for canBuy in [0, 1]: skip = dp[cur + 1][canBuy] if canBuy: do = dp[cur + 1][0] - prices[cur] else: do = dp[cur + 2][1] + prices[cur] dp[cur][canBuy] = max(skip, do) return dp[0][1]

[@ashkan.arabim]

I managed to do this with in a slightly simpler way such that dfs only takes the index of the array (and dp is just a 1d list): ``` class Solution: def maxProfit(self, prices: List[int]) -> int: dp = {} def dfs(i): # base case: out of bounds if i >= len(prices): return 0 # base case: dp if i in dp: return dp[i] # inductive case buycost = prices[i] maxprof = 0 for j in range(i + 1, len(prices)): # sell at this position sellcost = prices[j] prof = sellcost + dfs(j + 2) - buycost if prof > maxprof: maxprof = prof dp[i] = maxprof return dp[i] return max([dfs(n) for n in range(len(prices))]) ```

[@saihajgulati236]

the use of the word cooldown confused me a lot, but for anyone reading this, he uses it to refer a day when you CHOOSE to not do anything, while the problem uses it to refer to the day after you sell when you are FORCED to not do anything, which in his code is handled by the i+2 in the else statement.

[@cosepeter2197]

was able to do buy and sell stock with transaction fee with the same approach. Thanks

[@sadekjn]

I really wish you went over the state machine DP solution. Would have loved to see your explanation of it.

[@MAHADMahadmahad7852]

Damn, that's a nice way of thinking about it. I was trying to and able to solve it, but my solution wasn't as efficient and was only better than 10% of the solutions (O(n^2) complexity). Looked at this video and realized my way of caching/memoizing was the issue. Thinking about it in terms of just two decisions is so clever!

[@pamp3657]

14:55 for line 21, shouldn't cooldown be equals to dfs(i + 1, not buying) instead of dfs(i + 1, buying)? Since you have chosen to not sell and to have a cooldown instead, then as the index increments you CANNOT buy until you sell. dfs(i + 1, buying) would mean that you can choose to not sell, and then buy more stock before selling, which isn't allowed per the description rules.

[@dj1984x]

Yes, I agree. It looks to me like someone added a test case where the code he posted does not work, because as you stated line 21 is incorrect.

[@jerrychan3055]

@@dj1984x so how could we modify the code?

[@dumdum407]

@@jerrychan3055 you add this line to the buy if check: cooldown := dfs(i+1, 0) and this line to the sell if check. cooldown := dfs(i+1, 1) , In my solution, 0 == buying, selling == 1. The point is the cooldown dfs is different for buying and selling state

[@diabolicfreak]

Something which I dont understand, there are multiple nodes with (i, buying), how does memoization work correctly in this case?

[@JeiShian]

"I'm going to make this problem look like a joke today, not because I'm smart, but only because I know how to draw a picture" My man went from 🤓to😎real quick

[@anonymoussloth6687]

Can you do the other variations also? 1 transaction 2 transactions at most k transactions

[@LongNguyen-cn7dp]

Really appreciate your video. It's easy to understand, rather than some kinda state machine

[@aparnamane1164]

if in buy we are in opposite state (not buying) then in the else where we are selling the dfs call should be dfs(i+2, buying) right?

[@snehaldave4834]

Great explanation!!! True, you are good at drawing, I was able to solve puzzle iii and iv with the same drawing technique you used :)

[@dankquan743]

dfs with cache is much slower than the optimal solution. would love to see a series where you go back over these old videos and revise the solution

[@SemesterAtSeaHopeful]

What’s the optimal?

[@Messirobben047]

How did you come up with caching key?

[@habalgarmin]

my js solution: var maxProfit = function (prices) { const states = ['B', 'S', 'C']; const memo = new Map(); function backtrack(step, index) { if (index === prices.length) return 0; const currState = states[step % 3]; const k = `${index}-${currState}`; if (memo.has(k)) return memo.get(k); let res = 0; for (let i = index; i < prices.length; i++) { let price = prices[i]; if (currState === 'B') { price *= -1; } if (currState === 'C') { price = 0; } const btr = backtrack(step + 1, i + 1) + price; memo.set(k, Math.max(memo.get(k) || 0, btr)) res = Math.max(res, btr); } return res; } return backtrack(0, 0); };

[@himanshusoni1512]

Thank you so much for the smooth explanation. Your videos always help. Cheers!

[@franciscogutierrezramirez5497]

yeah the variable here is confusing, replace buying to canbuy

[@programmingrush]

I don't think DFS was needed in this case. It's making it more complicated. But anyways I follow your tutorials for the explanation which are amazing.

[@nataliasmith6721]

i agree

[@wij8044]

He explained the optimal solution, which requires dp since the complexity of recursive solution is 2^n. The use case of dp in general is to reuse existing solutions to significantly reduce time complexity, in this case reducing time complexity to O(n) since each node in memory is computed exactly once.

[@jerrychan3055]

Will not pass all the test cases as of now, one failed case is [2,1,2,1,0,1,2] and max profit should be 3. Instead, we can consider has stock or not: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = {} def dfs(i, has_stock): if i >= n: return 0 if (i, has_stock) in dp: return dp[(i, has_stock)] if not has_stock: buy = dfs(i + 1, True) - prices[i] cooldown = dfs(i + 1, False) dp[(i, has_stock)] = max(buy, cooldown) else: sell = dfs(i + 2, False) + prices[i] cooldown = dfs(i + 1, True) dp[(i, has_stock)] = max(sell, cooldown) return dp[(i, has_stock)] return dfs(0, False)

[@ibr0303]

@jerrychan3055 Can you please explain why the Neetcode solution doesn't work for this test case and yours does?

[@MegaZz-j9c]

can u please do best time to buy and sell stock iv? cant find good explanation video for that one

[@tranminhquang4541]

This is an insanely hard question imo . Shouldnt give it a "medium" at all!

[@andrepinto7895]

There is also a DP solution for this problem.

[@pikachuryan7393]

good website and good explanation, but not-ideal naming, took me forever to figure out; should've just asked GPT to write a dfs memo version for me. also I would think learning only-recursion solution is dangerous for anyone who want a good understanding. think for more.

[@sylvesterdzimiri3266]

Dude just found your channel and its amazing!!! Keep up the great work.

[@agnishwarbagchi4935]

The way you wrote buy with red and sell with green reminded me of crypto.. Great solution!! Keep it up.

[@tjsm4455]

I have already implemented the top-down(memoization) method and then wasted 4 hours in thinking for a tabulation method. I came here for tabulation method, why didn't he implemented it in tabulation method?

[@manibhushankumarsingh5196]

I had solve this problem only after seeing your diagram.

[@ambushedraccoon6408]

Great job! What tool Are you using for drawing?

[@vdyb745]

This explanation is very clear and on point. Thanks !!!!!

[@Hangglide]

Thanks for your great video! It would be better if you call "buying" state "buyingOrCooldown" and call "sell" state "sellOrColldown".

[@ultraman72]

Thank you so much! I've been waiting for this

[@NeetCode]

No problem, happy to help

[@sanjanarajan6144]

Thanks for the amazing video, made it very simple to understand. Can you please add a video for "Best Time to Buy and Sell Stocks with Transaction Fee" also, and explain how different it is from the cooldown version? Thanks in advance.

[@kuancs1]

I know im late but can I have an iterative solution from any of y’all?

[@timithecat]

def maxProfit(self, prices: List[int]) -> int: buy_cache = (len(prices)+2) * [0] sell_cache = (len(prices)+2) * [0] for i in range(len(prices)-1,-1,-1): buy_cache[i]=max(-prices[i]+sell_cache[i+1],buy_cache[i+1]) sell_cache[i]=max(prices[i]+buy_cache[i+2],sell_cache[i+1]) return buy_cache[0]

[@venkateshv626]

does including the cooldown in if else instead of before if else result in fewer function calls?

[@johns3641]

Super cool that you included the code in the description! Keep it up!

[@sohaibpanwala5893]

I'm a little embarassed, i didn't understand the coding solution. Don't you have to put a loop on the "i" and how can you call a function within it like def dfs(i, buying): and then buy = dfs(i + 1, not buying) in the function. I feel like there's a lot of background theory and code that i don't know yet.

[@derekyoungman3895]

You should probably watch some videos on recursion

[@davidlee588]

The base case in dfs is so hard to come up with, esp the second base case, almost impossible for me.

[@dawarepramod9816]

i dont understand the caching .... we are going to save the dp[i,buying] but i,buying can be same for the multiple positions like if our 1st example suggest that for: buy->sell->cooldown->buy->sell dp[4,sell]=+3, but for : cooldown ->cooldown->cooldown-> buy->sell it will again have dp[4,sell]=+2 same dp position have different values?? how is the caching working here?? can anyone explain and help me ...????

[@andriidanylov9453]

Great solution. Thank You

[@jerrykuo8736]

You should add a donate button! Every time I get a question that you have a video on, I will donate 5 bucks!

[@juliuscecilia6005]

This is the greatest channel

[@arunraju9705]

Beautiful, man. I appreciate your videos.

[@friction5001]

I did an assignment similar to this on Java it was an electronic trading platform

[@praveenugiri]

Great Explanation, Thanks!

[@Tensor08]

You put dp, caching ,dfs, recursion into one and make a blend out of it after drewing it, not much efficient but still insanely genius man!!!

[@sidazhong2019]

Damn it I almost got this one, I missed i+2 for sell. I still think it is i+1.

[@qingyangsun434]

13:30 I still don't get it why sell = dfs(i+2, not buying) + price but not dfs(i+2, buying) + price, since after the cooldown, it's allowed to buy again right?

[@happymind6908]

because "buying" is in false state and you want to make it "true" for buying, so "not buying(false)" will make it true

[@qingyangsun434]

@@happymind6908 Thank you so much!

[@ziyangji9485]

@@happymind6908 but dfs(i + 1, not buying) will also be ''true" for buying right? but we cannot buy again right? i don't get why both buy and sell go with ''not buying"

[@Demandd]

This part got me so confused as well. Would have been a lot clearer if True/False passed in instead of buying/not buying

[@Demandd]

​@@ziyangji9485 not buying=False for the buying if statement block. The if statement block for buying executes if buying=True. So buy=dfs(idx+1, not buying) is equivalent to dfs(idx+1, not True), i.e. False The else block for selling executes if buying=False. So sell=dfs(idx+2, not buying) is equivalent to dfs(idx+2, not False), i.e. True here is the code using True/False instead of buying/not buying: class Solution: def maxProfit(self, prices): dp = {} def dfs(idx, buying): if idx >= len(prices): return 0 if (idx, buying) in dp: return dp[(idx, buying)] if buying: buy = dfs(idx+1, False) - prices[idx] cooldown = dfs(idx+1, True) dp[(idx, buying)] = max(buy, cooldown) else: sell = dfs(idx+2, True) + prices[idx] cooldown = dfs(idx+1, False) dp[(idx, buying)] = max(sell, cooldown) return dp[(idx, buying)] return dfs(0, True)

[@YeetYeetYe]

Why do we have a cooldown state for buying? I thought cooldown only applies after we sell? Is the cooldown here more like a "skip buying or selling this stock" ?

[@chef8776]

Once you have bought a share you can either Sell it or you not sell it. Not selling can be thought of as Cooldown where you are not involved in any transaction. Eitherway of thinking will result in unchanged profit.

[@geekydanish5990]

cooldown is choice not an enforced decision in case when we buy

[@sirrus3009]

I dont know if I you could ever come up with this solution on my own

[@uniquename2386]

Great solution, thanks!

[@hoyinli7462]

thx for ur video again. you saved me a lot of time!

[@MrLeyt1125]

Where is Buy or sell III video? We miss it

[@janardannn]

there is an O(n) greedy solution i guess, no dp, no table, no memo

[@anjanobalesh8046]

So clean so precise 😍

[@vartikasingh6812]

Awesome explanation. Thanks

[@mdjabirhossain173]

Why is it included in 2d dp problems in neetcode?

[@gonglarry9933]

dude, thanks for the great work

[@brokecoder]

I don't get why the cooldown for selling is not `cooldown = dfs(i+2,buying)'

[@themagickalmagickman]

cooldown could better be called 'do nothing' because thats what is really happening. The actual cooldown after selling is skipped over because there is no point in calculating (thats why we do i+2 when selling, we jump over the index because we would have just skipped it anyways). If you look at the decision tree, there is only 1 option after selling and that is to skip the next position, so why not just jump over it? Basically, we arent forced to sell, so we need to choose to either sell at this position or do nothing at this position. Thats why cooldown for selling is i+1, think of it as 'do nothing' instead.

[@techno-tronics4946]

memo = {} def buy_sell_cooldown(prices, buy, i=0, profit=0): if i >= len(prices): return profit key = (i, buy) if key in memo: return memo[key] cooldown = buy_sell_cooldown(prices, buy, i+1, profit) if buy: bought = buy_sell_cooldown(prices, False, i+1, profit - prices[i]) memo[key] = max(bought, cooldown) else: sell = buy_sell_cooldown(prices, True, i+2, profit + prices[i]) memo[key] = max(sell, cooldown) return memo[key] Why is this not working? Recursion without memo is giving correct output but as soon as I introduce memo it messes the output up.

[@elachichai]

prices : List[int]) -> int: What semantic is this in Py?

[@NeetCode]

Just type hints I think, they are not enforced tho

[@lightlysal]

I managed to solve this problem with just a 1-D DP memo. However, it seems to run much slower than your solution. Could someone explain the differences and why this is? Code: class Solution: def maxProfit(self, prices: List[int]) -> int: memo = [None for _ in range(len(prices))] def dp(i): # func assumes we are ready to buy! if i >= len(prices): return 0 if memo[i] is not None: return memo[i] maxProfit = dp(i + 1) # represents not buying for j in range(i + 1, len(prices)): # j is a location we can sell at maxProfit = max( maxProfit, prices[j] - prices[i] + dp(j + 2) # j + 2 is a location we can think abt buying again ) memo[i] = maxProfit return maxProfit return dp(0)

[@mattmendez8860]

Your time cmoplexity is O(n^2) because you're iterating over the range while inside the `dp` function you've written! It's technically more like O(n * n / 2) but still exponential

[@lightlysal]

@@mattmendez8860 I see, thank you!

[@danishpasricha4121]

great explanation

[@eeee8677]

This was SO helpful

[@selvamanigovindaraj4643]

Its very helpful

[@utkarshbhatnagar9178]

there is also a O(1) space solution can you please explain it (like a follow up on this video)...

[@Aashuthosh]

Me who shorts in the stock market....WHY CAN'T I SELL BEFORE BUYING!!!

[@creatorsresource8027]

This is top-down DP right?

[@geekydanish5990]

yes recursion + memoization

[@jesseli7086]

fast than 35.40% is pretty efficient ? why don't you turn the DFS into 3D-finite state machine to reduce the time and space cost ?

[@alanjamey2777]

Hello can you tell me what ide you use??

[@NeetCode]

I use the leetcode ide with the theme changed to 'monokai'

[@pamp3657]

very good video

[@jakubucinski]

Simpler solution : # dp[i][j] -> max profit with stock bought on i and sold on j # dp[i][j] -> prices[j] - prices[i] + max profits until i - 2 class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 maxes = [0] * len(prices) for i in range(len(prices)): for j in range(i + 1, len(prices)): adder = 0 if i >=2: adder = maxes[i-2] maxes[j] = max(maxes[j], prices[j] - prices[i] + adder, maxes[j-1]) return maxes[-1] Space complexity : O(n) Time complexity: O(n^2)

[@selva279]

Not all heroes wear a Cape...thanks a lot

[@ashutoshranaiiitdharwad8143]

giving TLE in c++ with same code

[@mohamedmoselhy]

Neet: I came up with a genius solution and here is how it works Parents 15:02: Why not 100% faster?

[@nikhildinesan5259]

Thnxx man...

[@rayahhhmed]

"I will make this question a joke today, just cause I can draw a picture" - Neetcode

[@true_human_007]

THIS DOES NOT WORK FOR [1,2,4]

[@katearcher8881]

I just checked: it does work for [1,2,4]

[@hualiang2182]

14:56, can initial buying state also be false? e.g. return Math.max(dfs(0, true), dfs(0, false))

[@ZVEKOfficial]

No, if you set it to false that means you would be selling on the 0th day, which is not possible since you don't own any stock on the 0th day