DP 37. Buy and Sell Stocks III | Recursion to Space Optimisation

[@nisanduathsara5242]

This time I was able to solve this problem on my own before watching the video and got accepted. Thank you Striver for your entire DP playlist without your playlist I couldn't solve any DP problems.

[@lavanya_m01]

The Nx4 solution is amazing and very intuitive. Thanks a lot for explaining multiple solutions to the same problem!

[@TheNishant30]

10:41. i always knew he was a man of culture.

[@parvahuja7618]

my man proved it again at 12:39

[@utkarshiitbhu4204]

butt butt

[@dhruvchopra26]

I thought i was the only one noticing this since the start of this dp series, poor striver doesnt even realize😂😂

[@vaibhavrawat4008]

kyu ni hori padhai 😂

[@yashshukla1637]

LMAO

[@mohitagarwal3639]

Hey Striver you have developed my thought process to a far extent..... I was able to space optimise this question to just 1 cur 2D vector without even using prev..... This is possible only because of you. I tried to think what does it require to fill a cell and then realized that using only cur would also work.... Thanks a lot.....you are my motivation

[@divyamgupta-t3i]

I have intentionally given very much time to DP 36: to buy and sell stocks unlimited time and it helped. I have done all the remaining question without seeing the solution videos. Thanks STRIVER. UNDERSTOOOOOOOD😃

[@NitinTak-j5j]

This is the first time i solved Leetcode hard myself because of u Striver. Thank u so Much for this kind of teaching.

[@akashsuklabaidya8196]

Recursion is magic ❤

[@rahulraj94391]

and Striver is the magician 😂

[@gauravagrawal7988]

@@rahulraj94391 🤣🤣

[@gauravagrawal7988]

The only magician who teaches magic

[@sahilgagan2242]

66.6% done , thanks striver broo to make me able to solve any of the dp pattern learn so far in this series.

[@Dontpushyour_luck]

Did this question upto the space optimization part all by myself without seeing the video. Thank you striver for such quality content in your dp series.

[@aneetupadhyay8857]

Awsm explanation buddy , Thank you :) whoever feels DP is hard , just follow along with this series and you will be able to solve questions by yourself.

[@raghavmanish24]

4 trike to bta hi diye , 1 aur bta dena tha 5 complete ho jate......you are amazing striver.....thankuuuuu

[@AbhinavChandel-s4l]

watching this video finishes the stock pattern for me thanks a lot striver

[@stith_pragya]

UNDERSTOOD........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@lakshsinghania]

i solved the entire problem on my own from recursion -> memoization -> tabulation -> space optimization thnk u striver

[@ishasharma4559]

Striverrrrrrrr i cant thank you enoughhh, i never thought i would ever be able to solve a hard ques by myself and that too of dp :) but I did this on my own a big big bigggggg thank you and shout out to you :) thanku soooo much❤❤you are a magician❤

[@eshupatel3902]

Bhaiya before folowing this series I just start by tabulation in dp problems and ends up doing nothing , but you have taught so beautifully that now when I see a new question, first I try to do it by recusion and then convert it to memoization or tabulation. Thanks Bhaiya for this amazing series.

[@VinayKumar-xs6el]

Thanks is small thing U did great job so many people learning from you.

[@paridhijain7062]

Understood, I wasn't not consistent from past 1 week, but still trying to practice daily on DP at least. Thank you for this Holy Playlist for DSA learners out there.

[@ScienceSeekho]

Welcome!

[@iWontFakeIt]

@@ScienceSeekho simp!

[@aayushbisht4307]

@@ScienceSeekho who tf are you?

[@prathameshkodgire8642]

Ooh what happened Paridhi why weren't you consistent??

[@mr.jacker3951]

simp

[@Abcd-jt1qs]

Thank you so so much Striver. I did the recursion, memoisation, tabulation and space optimisation approach on my own. The n*4 dp array approach is really good. UNDERSTOOD :)

[@arjunrai4937]

I watched all dp videos before this one and was able to solve this question on my own without watching the video. thank you so much striver...your teaching is really tremendous.

[@imPriyansh77]

I wasn't able to solve, but got a feeling of using another parameter to count the number of transactions left.

[@ritikshandilya7075]

predicted for first time the solution even its hard problem , Thankyou so much for providing conceptual understanding Striver

[@dolbyagarwal9316]

Thanks Striver so much. I was able to do recursion and memoization earlier, but i could just never relate it to tabulation and never ever did space optimization. Today I am confident if I have done recursion, I can go all way till optimizations.

[@Rkv224]

I was able to get to N x 4 solution by my own. I can't believe this. You are greatest teacher. Thank you so much ❤

[@sidduroy9150]

i can defintely say that i would die with out learning DP , if i didnt met striver, for every problem , he is keeping every possible solution,thats a great way though, thank you for providing this playlist , u are a way providing a new life for many people ,who are watching this , my all love for you boiiii

[@prateekanand4213]

Wow with last method we will have Time complexity of O(N*4) and space compelxity of 2*O(5) (after space optimization) that's great!!!

[@mlkgpta2869]

Thanks for the whole series, i have solved each and every problem till now and now i feel confident, will do cp a lot to gain speed and practice more.

[@LovepreetSingh-wq9ee]

Another way to frame this question. Given an array, Find the max value of a - b + c - d such at index of a is less than index of b, index of b is less than index of c and index of c is less than index of d.

[@tgayush1424]

Awesome bro , dp ke series dekh ke , ab pehla task recusive solution likhna rehta hai, uske baad toh fir memoisation, tabulation , space optimisation ab easily ban raha hai . DP is not that tough, which i was expecting, even today i learned 3D dp, before i was thinking aree yeh sab kya hai 3d ,4d dp,kitna hard hoga. Thanks ❤❤

[@prabhakaran5542]

Understood both ways dp[n][2][3] & dp[n][4] ❤

[@SnehJoshi19]

Happy Guru Purnima coding Guru 🙇

[@hrituraj5973]

understood bhaiya .this is your one of the best series bhaiya. thank you bhaiya

[@bhaktisharma9681]

Understood!! Thank you so much bhaiya!!

[@HevelGaming]

in this we should also consider a case when we reached at the the end index and still we are holding the stock that is buy = 1 that will not affect the ans but we shoul return int_min in that case

[@tanmayarora6659]

Thank You Striver!! You explained it so well, really a gem bro, I solved this one & next part of this myself without watching. Hats off to you!

[@055muditsingh7]

With your guidance , i am able to solve all types of buy and sell stock problems.

[@chetanraghavv]

in tabulation, first base case can be skipped as we are already initializing the vector with zeroes. we can skip second as well but with a slight change that we can run the inner loop from cap = 2 to cap > 0 instead of cap >= 0 because we know that when cap is 0, the profit is 0 so do not disturb that value.

[@amorphous4768]

no words for your contribution to all DSA learner :-))))

[@abinash1878]

As usual, Understood and u are the best.

[@rahulkhandelwal7034]

Thank you very much for providing DP tutorials . pls bring Next Series on Segment trees , fenwick tree .

[@ShubhamVerma-hk9qt]

hi striver bhaiya i did this problem without even watching the video for a second using 3D dp. Thanks to u bhaiya

[@MadhurGupta-f7p]

bhai bahut tagda samjhate ho yaar all clear

[@kaushik.aryan04]

I solved this my self from recursion to tabulation. This is the best dp playlist

[@KartikRai-YrIDDCompSciEngg]

space optimised int n=prices.size(); vector before(5,0); vector after(5,0); for(int i=n-1;i>=0;i--){ for(int t=3;t>=0;t--){ if(t%2==0) after[t] = max( -prices[i] + before[t+1], before[t] ); else after[t] = max( prices[i] + before[t+1], before[t] ); } before=after; } return after[0];

[@preetisahani5054]

Awesome explanation both N*2*3 and N*4

[@saunaknandi1814]

Raj Vhaiya the technique using 4 variables is derived from Buy and Sell Stocks I.

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@chakradharreddy6437]

I hope you guys are doing extremely well

[@codecreateriitp4751]

hii striver thaanks i clearly understand dp for your playlist thanks bhai

[@KhushiVerma-y6t]

Ultimate explanation 👍👍

[@sarankumaar6009]

did without even watching video. all credit goes to you bro thanks :)

[@KunalKumar-tp1cc]

Space Optimised Code :- int maxProfit(vector&price){ int n = price.size(); vector next(5,0),curr(5,0); for(int i=n-1; i>=0; i--){ for(int tran = 3; tran>=0; tran--){ int profit = 0; if(tran&1) profit = max(price[i] + next[tran+1], next[tran]); else profit = max(-price[i] + next[tran+1], next[tran]); curr[tran] = profit; } next = curr; } return next[0]; }

[@ntgrn-pr5yx]

thank you striver , understood

[@dhanashreegodase4445]

last solution was impossible for me to think.. awesome😁🤐

[@shivansh.speaks]

Kudos to you man!!!!

[@satyamsrivastava3423]

recursive dp is giving tle because in the dp declaration you have give size of 'n' rather it should be 'n+1'

[@tusharnain6652]

bro, n is right, recursive solution will always give tle, because of exponentioal tc

[@shashankarora2945]

Very good explanation

[@devbhattdev1607]

how can i able to see the notes of this perticular problem inorder to revise the logic behind it. please help me anyone

[@ajitpalsingh606]

@takeUforward Striver Sir! only two condition are required for base case conditon for tabulation !!! dp[n][0][0] = dp[n][1][0] = 0;

[@chinmaypanchal2521]

Done with my own sir 😎thankyou and god bless you 🥰

[@RogithRog]

For Java, Developers, I think this is easy way public static void main(String[] args) { int arr [] = {3,3,5,0,0,3,1,4}; int max = Integer.MIN_VALUE; int max1= Integer.MIN_VALUE; int temp =0; for(int i=0;ii) { temp = arr[i+1]-arr[i]; if(max

[@mriduljain6809]

Code for the last approach: Memoization: int help(int i,int t,vector &prices,vector &dp) { if(t==4)return 0; if(i==prices.size())return 0; if(dp[i][t]!=-1)return dp[i][t]; if(t%2==0) return dp[i][t]=max(-prices[i]+help(i+1,t+1,prices,dp),help(i+1,t,prices,dp)); else return dp[i][t]=max(prices[i]+help(i+1,t+1,prices,dp),help(i+1,t,prices,dp)); } int maxProfit(vector& prices) { int n=prices.size(); vector dp(n,vector (4,-1)); return help(0,0,prices,dp); } Tabulation int maxProfit(vector& prices) { int n=prices.size(); vector dp(n+1,vector (5,0)); for(int i=n-1;i>=0;i--) { for(int t=0;t=0;i--) { for(int t=0;t=0;i--) { for(int t=0;t

[@its-itish]

Understood! Thank you..

[@chandrachurmukherjeejucse5816]

Understood. Solved the problem by myself. Great teaching striver

[@djpsn7094]

note! 17:50 it is cap and buy can be anything

[@prateeksharma3698]

Space optimized code for last approach - int f( vector &prices , int n){ vector ahead(5,0) , curr(5,0); for(int i = n-1 ; i>=0 ; i--){ for(int j = 0 ; j

[@tusharnain6652]

Bro you can also optimize this to Single Array, here is the code int maxProfit(vector &prices) { int n = prices.size(); vector dp(5, 0); // base case // just initialize the linear dp with 0 for (int index = n - 1; index >= 0; index--) { for (int transaction = 3; transaction >= 0; transaction--) { int profit; if (transaction % 2 == 0) { int buying = -prices[index] + dp[transaction + 1]; int not_buying = 0 + dp[transaction]; profit = max(buying, not_buying); } else { int selling = prices[index] + dp[transaction + 1]; int not_selling = dp[transaction]; profit = max(selling, not_selling); } dp[transaction] = profit; } // dp = temp; } return dp[0]; }

[@praveenkumarinti9047]

Tabulation for last one in python: dp = [0,0,0,0,0] for i in range(n-1,-1,-1): temp = [] for j in range(4): if(j%2==0): profit = max(-prices[i]+dp[j+1], dp[j]) else: profit = max(prices[i]+dp[j+1], dp[j]) temp.append(profit) temp.append(0) dp = temp return dp[0]

[@AmitYadav-gf9hm]

Best Series for Stock Problems ,Love it.

[@ammanchhetri6716]

able to solve this probelm on own...thanks for ur hardwork...

[@vishalarora3581]

**** ALL CODES OF THIS VIDEO BELOW INCLUDING LAST PART OF Nx4 DP with space optimisation **** #include using namespace std; //Memoization int f(int idx, bool buy, int cap, vector &prices, int &n, vector &dp){ //Base Cases if(idx == n || cap == 0)return 0; if(dp[idx][buy][cap] != -1)return dp[idx][buy][cap]; //Explore all paths if(buy){ return dp[idx][buy][cap] = max( -prices[idx] + f(idx+1, 0, cap, prices, n, dp), 0 + f(idx+1, 1, cap, prices, n, dp)); } return dp[idx][buy][cap] = max( prices[idx] + f(idx+1, 1, cap-1, prices, n, dp), 0 + f(idx+1, 0, cap, prices, n, dp)); } int maxProfit(vector& prices, int n) { vector dp(n, vector(2, vector(3,-1))); return f(0, 1, 2, prices, n, dp); } //Tabulation int maxProfit(vector& prices, int n) { vector dp(n+1, vector(2, vector(3,0))); for(int idx = n-1; idx>=0; idx--){ for(int buy = 0; buy=0;idx--){ for(int ts = 3;ts>=0;ts--){ if(ts%2==0){ cur[ts] = max(-prices[idx]+ahead[ts+1],ahead[ts]); } else{ cur[ts] = max(prices[idx]+ahead[ts+1],ahead[ts]); } } ahead = cur; } return ahead[0]; } int main() { return 0; }

[@vaibhavvashist238]

can u do bottom up for this approach or bottom-up is not possible?

[@aasthaaggarwal8909]

this series made our life easier. thanks striver

[@himanshuagrawal8012]

4 Solution mentioned (Memoized CODE , Tabulation code , Space Optimized with 2 Array ,Space Optimized with 1 D array ) I ❤ you Striver. Memoized CODE :- class Solution { public: int recur(int i,int trans,vector & nums,int n, vector& dp) { if(i == n || trans == 4)return 0; if(dp[i][trans] != -1)return dp[i][trans]; if(trans % 2 == 0) { return dp[i][trans] = max(-nums[i] + recur(i+1,trans+1,nums,n,dp) , recur(i+1,trans,nums,n,dp)); } else { return dp[i][trans] = max(nums[i] + recur(i+1,trans+1,nums,n,dp) , recur(i+1,trans,nums,n,dp)); } } int maxProfit(vector& prices) { int n = prices.size(); vector dp(n,vector (4,-1)); return recur(0,0,prices,n,dp); } }; ================================================================================================ Tabulation code :- class Solution { public: int maxProfit(vector& nums) { int n = nums.size(); vector dp(n+1,vector (5,0)); for(int i=n-1;i>=0;i--) { for(int trans = 3;trans >= 0;trans--) { if(trans % 2 == 0) { dp[i][trans] = max(-nums[i]+dp[i+1][trans+1],dp[i+1][trans]); } else { dp[i][trans] = max(nums[i] + dp[i+1][trans+1] , dp[i+1][trans]); } } } return dp[0][0]; } }; ================================================================================================== Space Optimized with 2 Array :- class Solution { public: int maxProfit(vector& nums) { int n = nums.size(); vector next(5,0); for(int i=n-1;i>=0;i--) { vector curr(5,0); for(int trans = 3;trans >= 0;trans--) { if(trans % 2 == 0) { curr[trans] = max(-nums[i]+next[trans+1],next[trans]); } else { curr[trans] = max(nums[i] + next[trans+1] , next[trans]); } } next = curr; } return next[0]; } }; ================================================================================================= Space Optimized with 1 D array:- class Solution { public: int maxProfit(vector& nums) { int n = nums.size(); vector next(5,0); for(int i=n-1;i>=0;i--) { for(int trans = 0; trans

[@businessburstx]

Bhai 1d ya 2d array se space kaise optimize ho rha hain auxilary stack toh 0(n) hi hoga na abhi bhi ???

[@himanshuagrawal8012]

@@businessburstx Ha time complexity same hai..but 1d array me bhi possible hai solution

[@mohitsingh13]

Understood ❤

[@siddheshdeshpande5258]

Why do i need to put cap also a part of dp why just keeping it as a parameter doesnt work??

[@vikasgupta6701]

Able to solve using the concept of prev. problem. Thanks Striver!!

[@adityaanand8473]

Understood everything. Here is the space-optimized code you asked for: class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int cap = 2; bool buy = true; vector t(n+1, vector(5, 0)); vector prev(5, 0), cur(5, 0); for(int i=n-1; i>=0; i--){ for(int j=0; j

[@sudo_ayush]

will anyone clarify this for me: i get confused when i go for tabulation what should we return , what should be the size of dp array sometimes n sometimes n+1 (why when we tend to use n in memoization why not use that ) similarly initialisations with 0 instead of -1

[@darish155]

Understood!!!! Thank you so much Striver.

[@satishtiwari9753]

Thank you Striver Sir for such a amazing DP series...

[@prathameshkodgire8642]

Welcome

[@manshishreya1282]

tabulation with space optimisation:- int maxProfit(vector& prices, int N) { n=N; vector curr(5, -1); vector aft(5, -1); int buy =1; for(int i=n;i>=0;i--){ for(int count=0;count

[@242deepak]

it doesn't work if I use cap for buying stock instead for selling. why is it so? can someone help?

[@rajatraj4297]

DP(N x 4) Space Optimization Soln: int maxProfit(vector& prices) { int n = prices.size(); vector after(5,0) , curr(5,0); for(int ind = n-1;ind>=0;ind--){ for(int trans = 3;trans>=0;trans--){ int profit; if(trans % 2 == 0) // buy profit = max(-prices[ind] + after[trans+1] , after[trans]); else profit = max(prices[ind] + after[trans+1] , after[trans]); curr[trans] = profit; } after = curr; } return after[0]; }

[@utkarshvishwakarma604]

thankyou. you made 3d dp so simple nd easy

[@muskanpoddar7774]

int n=price.size(); vector after(4+1,0); vector curr(4+1,0); for(int ind=n-1;ind>=0;ind--){ for(int trans=3;trans>=0;trans--){ if(trans%2==0) curr[trans]=max(-price[ind]+after[trans+1], after[trans]); else curr[trans]=max(price[ind]+after[trans+1],after[trans]); } after=curr; } return after[0];

[@jayujain2647]

Can someone explain why we are using a vector of size 3 for cap in memoization? I think we are not storing for cap=0?

[@knowledge-n9z1w]

Why in tabulation, you are increasing n to n+1 in dp array?? but not in memoization code ? ?

[@GhostVaibhav]

Understood🔥

[@stanleyalfred5076]

why during tabulation we always create dp[n+1] as opposed to memoization dp[n] ?

[@saurabh7650]

i came up with the solution with similar to second method 27:02

[@jiotv7923]

in the code of tabulation part why you didn't write the base case .....can someone say

[@jidgesanathkumar8038]

NUV DEVUDIVI SAAMI🙏🙇🙇🙇

[@arkasheikh3539]

in any case you are looking for the java solution :) Space optimization: class Solution { private int helper(int[] prices , int ind , int buy , int cap , int dp[][][]){ if(ind == prices.length || cap == 0) return 0; if(dp[ind][buy][cap] != -1) return dp[ind][buy][cap]; int profit = 0; if(buy == 1){ profit = Math.max(-prices[ind] + helper(prices , ind+1 , 0 , cap ,dp) , helper(prices , ind+1 , 1 , cap ,dp)); }else{ profit = Math.max(prices[ind] + helper(prices, ind+1 , 1 , cap-1 ,dp) , helper(prices , ind+1 , 0 ,cap , dp)); } return dp[ind][buy][cap] = profit; } public int maxProfit(int[] prices) { int n = prices.length; int dp[][][] = new int[n][2][3]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < 2 ; j++){ for(int k = 0 ; k < 3 ; k++){ dp[i][j][k] = -1; } } } return helper(prices , 0 , 1 , 2 , dp); } } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Tabulation: class Solution { public int maxProfit(int[] prices) { int n = prices.length; int dp[][][] = new int[n+1][2][3]; for(int ind = n-1 ; ind >= 0 ; ind--){ for(int buy = 0 ; buy < 2 ; buy++){ for(int cap = 1 ; cap < 3 ; cap++){ int profit = 0; if(buy == 1){ profit = Math.max(-prices[ind] + dp[ind+1][0][cap] ,dp[ind+1][1][cap]); }else{ profit = Math.max(prices[ind] + dp[ind+1][1][cap-1] , dp[ind+1][0][cap]); } dp[ind][buy][cap] = profit; } } } return dp[0][1][2]; } } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Space optimization: class Solution { public int maxProfit(int[] prices) { int n = prices.length; int dp[][] = new int[2][3]; for(int ind = n-1 ; ind >= 0 ; ind--){ int curr[][] = new int[2][3]; for(int buy = 0 ; buy < 2 ; buy++){ for(int cap = 1 ; cap < 3 ; cap++){ int profit = 0; if(buy == 1){ profit = Math.max(-prices[ind] + dp[0][cap] ,dp[1][cap]); }else{ profit = Math.max(prices[ind] + dp[1][cap-1] , dp[0][cap]); } curr[buy][cap] = profit; } } dp = curr; } return dp[1][2]; } }

[@arihantjammar8888]

Understood 😊

[@shashankadiga7796]

in the previous question he returned dp[0][1] but here why are we returning dp[0][0][2]? shouldn't it be dp[0][1][2]?

[@AnkuGarg]

I was able to come up with the solution and coded it before watching the video but the test cases was not passing. Silly me, I assumed the second parameter given is the number of transaction to be made. So, I was passing `n` instead of `2`. After watching the video, I realised this mistake :P Thanks Striver for the amazing content, so far I am understanding and practising alot.

[@siddharthjain2451]

in tabulation we start from n-1 can we start from n =0 or n=1 ? if it is can someone tell the code

[@manojnavinjamuri5867]

understood thank you

[@Fakhrul-Islam-22]

Thanks brother ❤

[@himanshumishra4567]

Can someone please explain the swap part. How is that possible we just assigned after = curr. This should mean that curr and after are pointing to same vector right. Correct me if I'm wrong.

[@lakshaysharma6550]

UNDERSTOOD!!!!!!🔥🔥🔥🔥🔥

[@sahilgagan2242]

bhai tum konse year me ho