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/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
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...

[@faizanusmani2200]

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

[@techdose4u]

Thanks

[@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

[@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 😊

[@MrRobot-mb6rq]

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

[@techdose4u]

Thanks : )

[@rajatbudania6181]

Best explanation series on Buy And Sell Problems !!

[@techdose4u]

Thanks :)

[@mohinipotdar477]

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

[@annawilson3824]

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

[@techdose4u]

👍🏼

[@jaatharsh]

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

[@techdose4u]

Thanks

[@lapujain]

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

[@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.

[@tanvisharma6879]

Very well explained. Hats off to Tech Dose!

[@techdose4u]

Thanks :)

[@gurnoorsingh2954]

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

[@techdose4u]

Thanks buddy :)

[@subhascse]

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

[@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

[@vrushankrao4911]

Kicking off the day with this video 🔥

[@techdose4u]

Nice :)

[@MrACrazyHobo]

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

[@abhilakshmaheshwari9360]

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

[@dushyantsingh2624]

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

[@techdose4u]

Wow 😅

[@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 :)

[@BurhanWani1]

Great explanation. Keep up the good work

[@techdose4u]

Thanks :)

[@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).

[@saneethvarma7806]

Best Explanation for this problem.

[@techdose4u]

Thanks :)

[@EditorGuru]

Amazing explanation brother...Thank you so much

[@ajaywadhwa3398]

Wow !!! This is really an awesome explanation.

[@techdose4u]

Thanks

[@JyotiprakashMandal-bp8ng]

Divide and conquer easy damn easy thanks a lot

[@bharathkumar5870]

wow..that divide and conquour approach is super

[@MiddleClassTalk]

amazing devide and conqure approach

[@techdose4u]

Thanks 😄

[@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

[@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).

[@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.!!!

[@Mandeepsingh-jo5cf]

You are the Best .

[@yitingg7942]

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

[@techdose4u]

You are not just a student 🤪

[@sumashreyatv2506]

Amazing explanation....so easy to understand.

[@techdose4u]

Thanks :)

[@anmolsharma9539]

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

[@santoshreddy3]

You are awesome. Very nice explanation.

[@techdose4u]

Thanks

[@amchourasia]

Beautiful explanation

[@kunalsoni7681]

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

[@techdose4u]

Thanks :)

[@manasbohat6883]

thank you man , this was amazing

[@techdose4u]

Welcome :)

[@ajmalmohamed]

Awesome

[@techdose4u]

Thanks

[@MrKasle]

Great Explanation!!!

[@techdose4u]

Thanks

[@xiaoweidu4667]

Fantastic!

[@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.

[@meylyssa3666]

Nice explanation! Thanks!

[@techdose4u]

Welcome :)

[@kapilgupta8543]

Nice intuitive explanation!

[@techdose4u]

Thanks

[@seekimaan]

amazing explanation, thank you very much sir!

[@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.

[@Samir-ow6sq]

Good Explanation

[@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?

[@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 ?

[@vinothrajg8576]

Great stuff again ☺️.. Thank your

[@techdose4u]

Welcome :)

[@hoyinli7462]

thx for ur video!

[@BlumChoi]

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

[@souravsaha3446]

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

[@praveenbandaru8700]

why is time complexity 2^n for memoization?

[@vishalverma920]

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

[@MansiThakkar139]

Very useful! Thank you

[@techdose4u]

Welcome :)

[@siddharthmehta6966]

Simply , Loved it !

[@nikhilchandna4851]

Great Explanation

[@techdose4u]

Thanks

[@ashutoshtiwari4719]

Thank you !!

[@techdose4u]

Welcome :)

[@mystryb345]

very good explanation sir

[@techdose4u]

Thanks

[@Arunkumar-bo2wc]

Amazing

[@PawanKumar-tu6ti]

thank you sir.

[@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

[@yashjain992]

This is gold!!

[@techdose4u]

😁

[@shaheenrafiq5974]

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

[@vinayak186f3]

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

[@techdose4u]

😂

[@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.

[@mhaesh]

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

[@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...

[@golekhabhoi7356]

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

[@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..

[@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.

[@chaitanyabalanagu626]

divide and conquer @ 14:16

[@SHASHANKRUSTAGII]

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

[@SushilKumar-wt7js]

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

[@agnesakne4409]

I don't know

[@aleaf355]

Please add timestamps for long videos

[@techdose4u]

Sure

[@tharunkumarreddy1224]

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

[@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.

[@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 😅

[@ankushroy919]

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

[@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)

[@prateeksinghal630]

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

[@gladyouseen8160]

Sir can we solve this problem using state machine?

[@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.

[@witty_idipt]

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

[@tilakrajrao2753]

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

[@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

[@ashishg656]

Great :)

[@techdose4u]

Thanks :)

[@vaibhavaggarwal6808]

is any iterative solution possible

[@AshwaniKumar-tw8vp]

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

[@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

[@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??

[@2121sourabh]

GOD

[@techdose4u]

😅

[@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

[@SVW_SHA]

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.

[@momozkichutney]

Why t=0 is out of bound.
T

[@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?

[@fishraider7897]

I continue not to understand this problem. Maybe next time.

[@exodus5948]

Legends come at night 😁😁

[@techdose4u]

😂