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
2 жыл бұрын
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
2 жыл бұрын
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
2 жыл бұрын
That's a good point, I think "canbuy" is definitely a better name for it.
@sithlord3442
2 жыл бұрын
Thank you so much. I was struggling with this problem earlier in the day! Love your explanations
@shrimpo6416
2 жыл бұрын
I struggled with this one a whole afternoon and your video just saved my day!
@yunaf4609
2 жыл бұрын
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 :)
@dryng6006
2 жыл бұрын
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
11 ай бұрын
@@roshansaundankar4893 No, this is top-down DP. Bottom-up DP doesn't use recursion.
@wij8044
10 ай бұрын
Hash for cache -> top down
@JeiShian
10 ай бұрын
"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
@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
@rahulsbhatt
7 ай бұрын
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); }
@user-ee3is4xs5v
10 ай бұрын
I love the idea of deducting the price from profit when you buy the stock, simple trick but make it a lot easier
@pamp3657
11 ай бұрын
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
9 ай бұрын
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
6 ай бұрын
@@dj1984x so how could we modify the code?
@dumdum407
4 ай бұрын
@@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
@sk_4142
Жыл бұрын
I really wish you went over the state machine DP solution. Would have loved to see your explanation of it.
@josephmasinre1840
2 жыл бұрын
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)
@sylvesterdzimiri3266
2 жыл бұрын
Dude just found your channel and its amazing!!! Keep up the great work.
@ultraman72
2 жыл бұрын
Thank you so much! I've been waiting for this
@NeetCode
2 жыл бұрын
No problem, happy to help
@himanshusoni1512
2 жыл бұрын
Thank you so much for the smooth explanation. Your videos always help. Cheers!
@jerrychan3055
6 ай бұрын
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?
@anonymoussloth6687
2 жыл бұрын
Can you do the other variations also? 1 transaction 2 transactions at most k transactions
@Messirobben047
2 жыл бұрын
How did you come up with caching key?
@diabolicfreak
2 жыл бұрын
Something which I dont understand, there are multiple nodes with (i, buying), how does memoization work correctly in this case?
@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.
@programmingrush
2 жыл бұрын
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
2 жыл бұрын
i agree
@wij8044
10 ай бұрын
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.
@LongNguyen-cn7dp
2 жыл бұрын
Really appreciate your video. It's easy to understand, rather than some kinda state machine
@dankquan743
6 ай бұрын
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
@johns3641
2 жыл бұрын
Super cool that you included the code in the description! Keep it up!
@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!
@cosepeter2197
Жыл бұрын
was able to do buy and sell stock with transaction fee with the same approach. Thanks
@vdyb745
2 жыл бұрын
This explanation is very clear and on point. Thanks !!!!!
@arunraju9705
2 жыл бұрын
Beautiful, man. I appreciate your videos.
@sohaibpanwala5893
2 жыл бұрын
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
2 жыл бұрын
You should probably watch some videos on recursion
@snehaldave4834
2 жыл бұрын
Great explanation!!! True, you are good at drawing, I was able to solve puzzle iii and iv with the same drawing technique you used :)
@praveenugiri
Жыл бұрын
Great Explanation, Thanks!
@kuancs1
3 ай бұрын
I know im late but can I have an iterative solution from any of y’all?
@franciscogutierrezramirez5497
20 күн бұрын
yeah the variable here is confusing, replace buying to canbuy
@tranminhquang4541
7 ай бұрын
This is an insanely hard question imo . Shouldnt give it a "medium" at all!
@ambushedraccoon6408
9 ай бұрын
Great job! What tool Are you using for drawing?
@andriidanylov9453
Жыл бұрын
Great solution. Thank You
@andrepinto7895
2 жыл бұрын
There is also a DP solution for this problem.
@uniquename2386
Жыл бұрын
Great solution, thanks!
@juliuscecilia6005
2 жыл бұрын
This is the greatest channel
@hoyinli7462
2 жыл бұрын
thx for ur video again. you saved me a lot of time!
@anjanobalesh8046
Жыл бұрын
So clean so precise 😍
@selvamanigovindaraj4643
6 ай бұрын
Its very helpful
@Hangglide
2 жыл бұрын
Thanks for your great video! It would be better if you call "buying" state "buyingOrCooldown" and call "sell" state "sellOrColldown".
@friction5001
2 жыл бұрын
I did an assignment similar to this on Java it was an electronic trading platform
@vartikasingh6812
2 жыл бұрын
Awesome explanation. Thanks
@user-ce6zj1dt4s
Ай бұрын
can u please do best time to buy and sell stock iv? cant find good explanation video for that one
@sanjanarajan6144
2 жыл бұрын
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.
@gonglarry9933
Жыл бұрын
dude, thanks for the great work
@tjsm4455
3 ай бұрын
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?
@eeee8677
2 жыл бұрын
This was SO helpful
@venkateshv626
Жыл бұрын
does including the cooldown in if else instead of before if else result in fewer function calls?
@jerrykuo8736
2 жыл бұрын
You should add a donate button! Every time I get a question that you have a video on, I will donate 5 bucks!
@danishpasricha4121
2 жыл бұрын
great explanation
@MrLeyt1125
3 ай бұрын
Where is Buy or sell III video? We miss it
@davidlee588
Жыл бұрын
The base case in dfs is so hard to come up with, esp the second base case, almost impossible for me.
@dawarepramod9816
2 жыл бұрын
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 ...????
@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); };
@sirrus3009
9 ай бұрын
I dont know if I you could ever come up with this solution on my own
@qingyangsun434
2 жыл бұрын
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
2 жыл бұрын
because "buying" is in false state and you want to make it "true" for buying, so "not buying(false)" will make it true
@qingyangsun434
2 жыл бұрын
@@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"
@YeetYeetYe
2 жыл бұрын
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
2 жыл бұрын
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
2 жыл бұрын
cooldown is choice not an enforced decision in case when we buy
@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.
@sidazhong2019
11 ай бұрын
Damn it I almost got this one, I missed i+2 for sell. I still think it is i+1.
@mdjabirhossain173
Жыл бұрын
Why is it included in 2d dp problems in neetcode?
@pamp3657
11 ай бұрын
very good video
@nikhildinesan5259
2 жыл бұрын
Thnxx man...
@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.
@agnishwarbagchi4935
Жыл бұрын
The way you wrote buy with red and sell with green reminded me of crypto.. Great solution!! Keep it up.
@lightlysal
11 ай бұрын
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
7 ай бұрын
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
7 ай бұрын
@@mattmendez8860 I see, thank you!
@techno-tronics4946
2 жыл бұрын
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.
@jeffpeng1118
2 жыл бұрын
what would be the space complexity for this?
@jeffpeng1118
2 жыл бұрын
also O(n)
@rayahhhmed
2 жыл бұрын
"I will make this question a joke today, just cause I can draw a picture" - Neetcode
@elachichai
2 жыл бұрын
prices : List[int]) -> int: What semantic is this in Py?
@NeetCode
2 жыл бұрын
Just type hints I think, they are not enforced tho
@selva279
2 жыл бұрын
Not all heroes wear a Cape...thanks a lot
@Aashuthosh
Жыл бұрын
Me who shorts in the stock market....WHY CAN'T I SELL BEFORE BUYING!!!
@alanjamey2777
2 жыл бұрын
Hello can you tell me what ide you use??
@NeetCode
2 жыл бұрын
I use the leetcode ide with the theme changed to 'monokai'
@utkarshbhatnagar9178
2 жыл бұрын
there is also a O(1) space solution can you please explain it (like a follow up on this video)...
@manibhushankumarsingh5196
2 ай бұрын
I had solve this problem only after seeing your diagram.
@creatorsresource8027
2 жыл бұрын
This is top-down DP right?
@geekydanish5990
2 жыл бұрын
yes recursion + memoization
@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)
@mohamedmoselhy
2 жыл бұрын
Neet: I came up with a genius solution and here is how it works Parents 15:02: Why not 100% faster?
@ashutoshranaiiitdharwad8143
Жыл бұрын
giving TLE in c++ with same code
@Tensor08
2 жыл бұрын
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!!!
@true_human_007
2 жыл бұрын
THIS DOES NOT WORK FOR [1,2,4]
@katearcher8881
2 жыл бұрын
I just checked: it does work for [1,2,4]
@jesseli7086
2 жыл бұрын
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 ?
@hualiang2182
2 жыл бұрын
14:56, can initial buying state also be false? e.g. return Math.max(dfs(0, true), dfs(0, false))
@ZVEKOfficial
2 жыл бұрын
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
Пікірлер: 127