Best Time to Buy and Sell Stock III | Leetcode

This video explains a very important programming interview problem which is buy and sell stock 3 which is from leetcode 123.I have already explained buy and sell stock 2 and buy and sell stock with cooldown and the LINK for these are present below.In this problem, i have explained the solution along with intuition for solving the problem.I have first shown the solution using backtracking and recursion and then i have shown the optimization using multi state memoization array.I have also shown an alternate memoization technique which is by using key as string (containing all appended states) and value as maximum profit obtained for that state.I have also shown all possible state transitions for all possible choices.The second method is by using divide and conquer technique which is intuitive if we divide the entire stock days into 2 parts and we take the maximum profit from each part and just add them to get max profit.I have shown intuition with examples for solving using divide and conquer.At the end of the video,I have explained the code walk through for both the techniques.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOS:-
Best time to buy and sell stock 2: • Best time to buy and s...
Best time to buy and sell stock with cooldown: • Best time to buy and s...

[@arnavkarforma3015]

The solution of this can be much much simpler then it looks like initially
Just have to simply consider that when we are buying something we are paying -price[i] if we are selling smth we are getting money +price[i]
public int maxProfit(int[] prices) {
int oneBuy = Integer.MIN_VALUE;
int oneBuyOneSell = 0;
int twoBuy = Integer.MIN_VALUE;
int twoBuyTwoSell = 0;
for(int i = 0; i < prices.length; i++){
oneBuy = Math.max(oneBuy, -prices[i]);
oneBuyOneSell = Math.max(oneBuyOneSell, prices[i] + oneBuy);
twoBuy = Math.max(twoBuy, oneBuyOneSell - prices[i]);
twoBuyTwoSell = Math.max(twoBuyTwoSell, twoBuy + prices[i]);
}
return Math.max(oneBuyOneSell, twoBuyTwoSell);
}

[@techdose4u]

👍

[@sumitprajapati821]

Nice

[@vaibhavbhardwaj8895]

you demotivate me

[@mohinipotdar477]

Explained very well and smoothly converted complex problem into simpler one. Thanks for such wonderful video.

[@faizanusmani2200]

Subscribed right away. Cant imagine the amount of work this creator is putting in making these videos. Hats Off.

[@techdose4u]

Thanks

[@abhilakshmaheshwari9360]

Big cheers to you man, explained really well!!!!🙌

[@dhruvsharma6772]

Thank you very much for such a wonderful explanation.Intuition development is very Important rather than coding and learning formula for this problem and you have explained it in depth with appropriate examples. Please keep making videos like these.

[@techdose4u]

Thanks

[@nightmarauder2909]

I really like that you explained the thought process behind implementing memoization. Thank you for that!

[@techdose4u]

Welcome 😊

[@subhascse]

Wonderful!! Finally a very good explanation!! Thanks a lot.

[@jaatharsh]

thanks a lot, dude, ur detailed explanation definitely helped understand the crux of the problem.
keep up the great work.

[@techdose4u]

Thanks

[@AkshayKumar-xh2ob]

Was struggling with this question and the intuition behind the soln for the whole day. As always TECH DOSE saves the day.

[@rajatbudania6181]

Best explanation series on Buy And Sell Problems !!

[@techdose4u]

Thanks :)

[@vrushankrao4911]

Kicking off the day with this video 🔥

[@techdose4u]

Nice :)

[@anmolsharma9539]

This is some next level stuff thank you so much sir. you are the real deal.

[@EditorGuru]

Amazing explanation brother...Thank you so much

[@tanvisharma6879]

Very well explained. Hats off to Tech Dose!

[@techdose4u]

Thanks :)

[@lapujain]

Amazing explanation. Hats off to you for putting so much efforts.

[@techdose4u]

Thanks :)

[@MrRobot-mb6rq]

Why CZcams doesn't have option for liking more than once?
Great explanation man🔥

[@techdose4u]

Thanks : )

[@siddharthmehta6966]

Simply , Loved it !

[@seekimaan]

amazing explanation, thank you very much sir!

[@annawilson3824]

Awesome video! In principle, we don't need the 1st loop, and going further we can solve even in one scan.

[@techdose4u]

👍🏼

[@manasbohat6883]

thank you man , this was amazing

[@techdose4u]

Welcome :)

[@ajaywadhwa3398]

Wow !!! This is really an awesome explanation.

[@techdose4u]

Thanks

[@vinothrajg8576]

Great stuff again ☺️.. Thank your

[@techdose4u]

Welcome :)

[@bharathkumar5870]

wow..that divide and conquour approach is super

[@BurhanWani1]

Great explanation. Keep up the good work

[@techdose4u]

Thanks :)

[@saneethvarma7806]

Best Explanation for this problem.

[@techdose4u]

Thanks :)

[@gurnoorsingh2954]

I don't think this could have been explained better than you did

[@techdose4u]

Thanks buddy :)

[@jimsmith4739]

@techdose Why are we going from end to middle in case of the right side from center and why not go just like he left side which is (along the timeline and not against)

[@dushyantsingh2624]

watching his amazing explanation at 3:20 am while waiting for 4:20am

[@techdose4u]

Wow 😅

[@Mandeepsingh-jo5cf]

You are the Best .

[@BlumChoi]

Please explain how to choose the dividing line in the divide and conquer approach

[@robertmiller3765]

I think the string operation glossed over in the middle is actually O(1) (since the length of the string would be constant) as it's just concatenating 3 numbers (not n numbers).

[@amchourasia]

Beautiful explanation

[@hoyinli7462]

thx for ur video!

[@meylyssa3666]

Nice explanation! Thanks!

[@techdose4u]

Welcome :)

[@santoshreddy3]

You are awesome. Very nice explanation.

[@techdose4u]

Thanks

[@MansiThakkar139]

Very useful! Thank you

[@techdose4u]

Welcome :)

[@prateeksinghal630]

Can you please tell the time complexity of the memoized solution for this problem !!

[@xiaoweidu4667]

Fantastic!

[@sumashreyatv2506]

Amazing explanation....so easy to understand.

[@techdose4u]

Thanks :)

[@witty_idipt]

can you please tell how time complexity of state machine code will be O(n)

[@JyotiprakashMandal-bp8ng]

Divide and conquer easy damn easy thanks a lot

[@SHASHANKRUSTAGII]

Just tell me how will it come to my mind?
How can one think this optimal approach by own?

[@nimishabajpai6816]

Can anyone tell that in the preferred language if I have wriitten java in kick start competition then I will get only java to use in coding??

[@tilakrajrao2753]

what will the overall time complexity of memoization approach ??? please do reply

[@tharunkumarreddy1224]

could someone explain difference between buy and sell stock2 problem and buy and sell stock 3 problem

[@PawanKumar-tu6ti]

thank you sir.

[@vishalverma920]

what is the time complexity of recursive solution after memoization ??

[@MrKasle]

Great Explanation!!!

[@techdose4u]

Thanks

[@yashjain992]

This is gold!!

[@techdose4u]

😁

[@kapilgupta8543]

Nice intuitive explanation!

[@techdose4u]

Thanks

[@toose8388]

Isn't this divide and conquer approach O(n^2)? As you have to loop over each element, and for each element check all elements to its left and right? In fact, my implementation of this method exceeds time limit on leetcode...

[@Samir-ow6sq]

Good Explanation

[@VS-cy8oy]

I have doubt, how do we come up with divide and conquer approach. i mean, How do we come to know that create left and right array with values and summing up them will give us the result.Is there any logical sequence behind this summing technique, from left to right i understood, but from right to left i am unable to get on what ground we are confirmed that taking max will work. I am confused in that, Will be huge help if you can clear this doubt please. I have solved it with recursion, but that wasnt accepting on IB, so i came across your d&c approach, please clear this doubt, thanks and really appreciate your work..

[@praveenbandaru8700]

why is time complexity 2^n for memoization?

[@Suraj-lo7bg]

i should take max(profit, left[i]+right[i]) . if we take left[i-1] we're excluding a fact that ith element may be the maximum of left subarray and minimum of right subarray.... in that case. transaction where we sell on ith day while we bought from a day on left, is ignored. and if we have to sell and buy on same day... that's same as holding it, because left subarray ensures that we've already purchased before we're trying to sell. check for the input.. 1 2 3 4 5 . now consider 3 as pivot.. profit left = 1, and profit right = 5-3 = 2.. total profit = 3... but max profit is 4. 5-1.

[@pavittarkumarazad3259]

This needs to be pinned. I was facing the same issue and resolved this by myself but was looking for the explanation. Thanks :)

[@golekhabhoi7356]

After buying a stock fall in - 5% what is the calculatin of profit and loss kingly guide me

[@MrACrazyHobo]

For any newcomers, the divide and conquer approach is the easiest to understand.

[@kunalsoni7681]

Sir really very amazing 😍😊 video and explanation is seriously beautiful and 😍😍😍

[@techdose4u]

Thanks :)

[@MiddleClassTalk]

amazing devide and conqure approach

[@techdose4u]

Thanks 😄

[@rajeshadam978]

I think its somewhat complicated to explain but you explained well !
here is a easy approach :
class Solution {
public int maxProfit(int[] p) {
int pr1=0;
int pr2=0;
int mn1=Integer.MAX_VALUE;
int mn2=Integer.MAX_VALUE;
for(int i=0;i

[@ashutoshtiwari4719]

Thank you !!

[@techdose4u]

Welcome :)

[@Arunkumar-bo2wc]

Amazing

[@mhaesh]

Nice explanation. Can you please make video for Best Time to Buy and Sell Stock with transaction fee

[@souravsaha3446]

Nice sir but in real practice we can sell a stock before buying .Thank you for amazing explanation

[@thinkverse94]

One Query. Please Clarify @TECH DOSE
for example, prices = [1,2,3,4]
If we partition in price=2, ([1,2] [2,4]) OR ([1,2] [3,4]) ...which one is correct?
My question is, in the same day can we sell the stock first and buy the stock ? (i.e. [[1,2] [2,4]] / [[1,3][3,4]] / ...... )
Or, Sell and buy must be in diff day ?

[@rahulmistry9173]

Amazing!!!! Could you explain the time complexity after adding memoization to the recursive solution? You didn't mention that

[@MrVishal203]

I think, number of calls in that case will also be 2^n, only difference is it will not calculate all the cases as the repeated ones are already stored. Please correct if this is wrong.

[@nikhilchandna4851]

Great Explanation

[@techdose4u]

Thanks

[@vaibhavaggarwal6808]

is any iterative solution possible

[@manishgoyal5298]

Can you please suggest some more problems to practice peak valley approach.

[@techdose4u]

Other versions of this problem are on similar logic. I had covered more of such videos in challenges but don't remember the name 😅

[@SushilKumar-wt7js]

in memoization case time complexity would be O(2*3*n) => O(n) right?

[@agnesakne4409]

I don't know

[@gladyouseen8160]

Sir can we solve this problem using state machine?

[@Kevin-gf8mq]

Why do we need 3 states? At end of the day, there're only 2 states anyway, either hold cash or hold stock.

[@SHASHIKUMAR-pp4hg]

I did it in O(n) time and space still 5%,5% on leetcode!!!!!!!!!!!!!!

[@pamelamoore9608]

Don't feel bad ... I tried a bottom-up DP approach to this, allocating a jagged array which is essentially O((N^2)/2) space (each cell storing an int), where each row corresponds to the end of the subarray and the column corresponds to the beginning of the subarray, and I also approach this using a divide and conquer (i.e. partition the array in 2 pieces (for the 2 transactions), and calculate max profit per subarray (calculating just once), and I don't get any TLE, but I blow up memory about test case 202 (of 214). I'm now trying to figure out how I can calculate better the next partition based on the previous partition. It's vicious (that's why it's hard).

[@yitingg7942]

Wow you just never stop surprising me. I am speechless!! Can I be your student please ？！！！😉😉

[@techdose4u]

You are not just a student 🤪

[@mystryb345]

very good explanation sir

[@techdose4u]

Thanks

[@shaswatdas6553]

You should upload on Box stacking DP problem. No good content is available on this topic. Thanks in advance!! ❤️

[@techdose4u]

Okay I will try

[@shaswatdas6553]

@@techdose4u thanks!❤️ Can you do it sooner?😅 Interview date is near.

[@ashishg656]

Great :)

[@techdose4u]

Thanks :)

[@ankushroy919]

i dont understand why u are moving in opposite direction we can also move from the i th position towards nth position

[@dovyraj1272]

sir, nice explanation, but how to get idea , the idea is not striking at all, when i see a new kind of problem, please help

[@techdose4u]

Maybe divide and conquer don't strike but recursion should be intuitive if you had solved cooldown problem or if you have practiced enough on backtracking. So try to think about observations and try to see if a problem can be framed or converted to other problem. This was you can practice to improve yourself.

[@ajmalmohamed]

Awesome

[@techdose4u]

Thanks

[@drishtdyumnshrivastava5313]

that divide and conquer approach simultaneously gave me Goosebumps but also left me in awe by the pure beauty of the approach..... As always really appreciate your work.....thank you.!!!

[@abhishekkumargupta3043]

Can't we sell and then buy that same stock on the same day? Or, are we already taking that into account here in the mentioned process. Please explain.

[@techdose4u]

We can't sell before buying and we cannot perform multiple operations on the same day. Only buy or sell on a day. I had said about this in the video.

[@abhishekkumargupta3043]

@@techdose4u Yes seen that, but it's not mentioned in the given problem description. Apparently ,we have to assume that.
Well thanks for the reply. Cheers!

[@techdose4u]

Yea it was not clear.

[@aksay.3823]

The idea(Divide and conquer one) is kind of related to the candy peoblem in leetcode.

[@techdose4u]

👍🏼

[@aksay.3823]

@@techdose4u Hey how about when we generalize and say k transactions are allowed then we will have to apply the memoization approach?

[@hriteshupadhyaya4440]

your dp approach is not getting accepted on interviewbit.

[@techdose4u]

Maybe they want divide and conquer. Interviewbit may set their requirement for the most optimal. Try the same on leetcode with DP. It depends of what complexity they are expecting.

[@hriteshupadhyaya4440]

@@techdose4u ya It is fine for leetcode

[@shaheenrafiq5974]

It's almost like you've hacked the human brain. *_*
Cant believe I understood it in a single go!

[@utkarshpanwar2358]

how can i see the implemented class behind the function on leetcode . please help me

[@techdose4u]

I don't think you can.

[@utkarshpanwar2358]

@@techdose4u but i did many times now i forgot how i did that or may they removed that option

[@utkarshpanwar2358]

@@techdose4u you are doing good may i suggest you something which i feel you should work on that related to presentation

[@vivekbudge9706]

@@utkarshpanwar2358 check successfully submitted solution, there are bars....for all usecases... click b on bar ... it will show underline program

[@ArbitCode]

which software do you use sir? is it openboard

[@techdose4u]

Wacom pro sketch.io

[@vinayak186f3]

If you don't come up with the solution , ask the interviewer to explain it to you

[@techdose4u]

😂

[@seal0118]

how did you know all this, sir?
is there a book that teaches you how to tackle these problems ?

[@techdose4u]

There is no such book 😅

[@seal0118]

​@@techdose4u but sir, this is very unintuitive for me, how do i learn about all this?, this is the first time i see dp problem with more than 1 state

[@MagicalCreationAviCreation]

Sir I am solving leetcode challenges since from 1 and half month , but some of problem I can't able to solve by my own ,once I watch solution then I think that I don't know even simple logic also, then i feel sad, then i close the laptop,
sir can you give me any suggestions
I want to become like u sir,

[@techdose4u]

Just spend some time about thinking the problem. Try harder each time. If you can't solve then read editorials and try to code yourself. You will definitely improve :)

[@MagicalCreationAviCreation]

@@techdose4u yeah I will definitely do sir,thank you sir

[@starc701]

sir one request from deepest of my heart ,and soul . can u make its 4th part, which i consider the toughest among all. plz sir , plz i beg u.plz make it , placement session is going on.

[@techdose4u]

Okay I will make it.

[@starc701]

@@techdose4u and sir in ur telegram channel u said to ask questions there, but how can we message in a channel, telegram doesn't allow that, plz create a group sir, thank you very much sir

[@techdose4u]

I have created both group and channel. Join both. They have different uses.

[@starc701]

@@techdose4u oops i only saw the channel link, now i got it.

[@abhishekkumargupta3043]

why going backwards works?

[@abhishekkumargupta3043]

Ok, so i understand it. (* starts crying in background).

[@techdose4u]

??

[@abhishekkumargupta3043]

@@techdose4u why going backwards (i.e. selling first and buying later) or reversing timeline for 2nd array works?

[@aleaf355]

Please add timestamps for long videos

[@techdose4u]

Sure

[@chaitanyabalanagu626]

divide and conquer @ 14:16

[@svcba_hvac]

Would you please add subtitle in your video?

[@techdose4u]

I am trying. I hope it's fixed soon. I am getting some problem in auto-generated English sub.

[@exodus5948]

Legends come at night 😁😁

[@techdose4u]

😂

[@ayushgarg5929]

Shortest Code Ever:-
int maxProfit(vector& prices) {
int n=prices.size();
if(n==0)
return 0;
int k1=0,k2=0,b1=-prices[0],b2=-prices[0],K1,K2,B1,B2;
for(int i=1;i

[@AshwaniKumar-tw8vp]

𝙄 𝙖𝙢 𝙖𝙙𝙙𝙞𝙘𝙩𝙚𝙙 𝙩𝙤 𝙙𝙤𝙨𝙚𝙨 𝙜𝙞𝙫𝙚𝙣 𝙗𝙮 𝙏𝙀𝘾𝙃 𝘿𝙊𝙎𝙀.🔥🔥🔥🔥

[@2121sourabh]

GOD

[@techdose4u]

😅

[@akshay_madeit]

tooooooo many ads. :(