💸 Visit https://www.educative.io/anuj to avail discount on all courses on Educative! 💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags: #anujbhaiya #dsaone #leetcode
Ignore these tags:
best time to buy and sell stock leetcode best time to buy and sell stock stock buy and sell anuj bhaiya stock buy and sell leetcode maximum profit by buying and selling a share at most twice buy and sell stocks leetcode 121. best time to buy and sell stock stock buy sell to maximize profit stock buy and sell problem leetcode 121 stock buy and sell gfg leetcode stock span problem buy and sell stock leetcode maximum profit best time to buy stocks best time to buy and sell stock ii when to buy and sell stocks buy and sell stocks best time to buy stocks leetcode stock buy and sell problem leetcode best time to buy and sell stock iii best time to sell stocks leetcode best time to buy and sell stock buy and sell stock stock buy sell problem dsa when buy and sell stock dsa one buy and sell stocks for beginners maximum profit gfg best time to buy and sell stock i kadane’s algorithm stock buy sell leetcode best time to buy and sell stocks buying and selling stocks best time to sell stocks leetcode leetcode problems maximum profit by buying and selling a share at most k times best time to buy and sell stock with transaction fee kadane algorithm minimize the heights ii stock maximize anuj buy and sell maximum profit by buying and selling a share atmost twice rearrange array in alternating positive \u0026 negative items with o(1) extra space best time to buy and sell stock iv buy sell stocks dsa full course dsa using c++ leet code love babbar stock buy sell stock for profit stock maximize hackerrank stock profit stock span when to sell stocks a company has a number of products in stock coding question algorithms anuj bhaiya dsa best time to buy and sell stock leetcode python best time to buy and sell stock python buying and selling stocks for beginners count inversion dsa with java dynamic programming problems garry sandhu get saged largest sum contiguous subarray leetcode solutions maximum product subarray maximum profit by buying and selling share at most twice rain water tapping problem rain water trapping problem stock buy tcs buy or sell trapping rain water problem two sum leetcode c++ solution when share buy and sell 121 algorithm allocate minimum number of pages amazon online assessment test amazon salary anuj bhaiya java apna college apni kaksha python array program in java best time to buy and sell stock atmost b times best time to buy and sell stock ii leetcode best time to buy and sell stock with cooldown binary tree maximum path sum buy sell buy sell stock leetcode leetcode leetcode 121 best time to buy and sell stock leetcode leet code 121 leetcode 121 best time to buy and sell stock leetcode 121 python leetcode 121 solution leetcode 121 tutorial eric programming leetcode 121 leetcode solutions buy and sell stocks leetcode leetcode 2021 121. best time to buy and sell stock leetcode leet code 121 explained leetcode best time to buy and sell stock python leetcode leetcode stocks leetcode solution leetcode problems
Content
0 -> Hello, whats up guys, Anju here and welcome back to DSA 1 course
2.47 -> And in today's video we are going to talk about, very important and popular problem of array
6.095 -> Which is called stocks buy and sell
8.62 -> There are multiple Variants to day we will talk about 1 variant
9.762 -> In which you will buy and sell 1 stock
14.682 -> In this there are many other variants, in which you can buy and sell multiple stocks
18.576 -> About which we will talk in next video
20.603 -> there are many, like at most 2, at most k, this all are also there
23.727 -> But today we are going to do this question, stocks buy and sell No. 1
27.937 -> In this you are given a stock, and multiple prices of the stock during the day are given
32.998 -> So you already know the future prices
34.607 -> So suppose, this is the graph, over here it is prices of stock , that how much stock price will go up and down
40.035 -> And these are days
40.628 -> This does not happen in real world situation
43.138 -> You do not know, in future the stock price will increase or decrease
46.201 -> Otherwise its and only profit
47.957 -> But over here you know, about future, that what is going to be the stock price on which day
52.217 -> Your job is you have to buy 1 stock and sell 1 stock
57.116 -> So, You have to tell, on which day you will buy and on which day you will sell
59.926 -> SO that my profit can be maximized
61.73 -> So you have to return the maximum profit
65.304 -> Like over here I can see, when I will purchase it over here, and sell it over here,
70.897 -> So 1st, 2nd, 3rd, I purchased it on 3rd day and 4th, 5th 6th, on 6th day I sold this, so I can get the maximum profit
78.616 -> So this is the problem, you basically will be given an array, in that array you will be given price of every day
84.369 -> And you have to find when you should buy the stock and when you should sell the stock
90.327 -> So that my profit can be maximum
91.772 -> So this is the problem, think a bit about how can you solve this
95.207 -> After that we will move ahead
96.888 -> So this is our question, we are given stock prices of different days
100.432 -> So these are some price, and we have to tell that when we have to buy and when have to sell so that our profit can be maximized
104.928 -> Over here as you can see, that when the price is lowest, 1, that time I should buy this
111.614 -> And when the price is 9, I should sell this
114.87 -> So that 9-1=8 is my profit
119.517 -> I will get profit of 8 units
121.491 -> So you have to find this only, basically you can see also that I have to find minimum over here, and what is the maximum after that
131.023 -> And the subtraction of that both is my answer
134.275 -> But over here also there are many catches
136.532 -> Because first yo cannot sell and then purchase, first you will have to buy then only you can sell
142.043 -> So this cannot be done, that your 9 is here and 1 here, then you cannot say I will sell it on 9 and purchase it on 1, this cannot be done
148.332 -> First you have to purchase, after that only you can sell
150.727 -> Right? this is what happens normally also
152.105 -> So over here also it is the same
153.575 -> We can see many catches, so how we have to solve this
157.572 -> Over here one way is Brute force, it is necessary to bring brute force solution
162.417 -> Brute force is also a solution
163.667 -> You always have to remember this
164.993 -> So how the Brute force be over here, brute force can be basically that you go on each day and purchase on that day and think about days ahead
174.154 -> That I will sell on these days then, what will be the profit?
175.939 -> And the maximum profit is to be stored
178.42 -> This Means, you first went on this day when price was 3
183.317 -> And you checked for all the days after that, when can I have maximum profit
187.038 -> So for 3 I checked 5, 5-3=2
189.95 -> Then 1-3=-2
191.8 -> then 7-3=4, so 4 is more, you know 3 and 9 will benefit more, then you will move ahead and check for 5
201.641 -> And you will check all the days for 5, 1-5,7-5, this way you will move ahead
205.752 -> And this way also we will get it, see over here 1, and 9, 9-1=8, this is one possibility
211.398 -> But if you will see over here, there are 2 for loops
214.325 -> 1 for loop for buy, and 1 for loop inside this for loop, for the one which you sell
224.842 -> So, the inner for loop is here, due to which the time complexity is O(n2)
231.679 -> So, our complexity is O(n2)
236.096 -> And for sure we can optimize this, it was the brute force solution
240.345 -> So think how can you optimize this, how can you use space, how can I come to know about future in advance
245.156 -> Think about these things, so if you might have thought about using space, then you can see if you can anyhow come to know the maximum ahead
253.397 -> Then we can assume that we have to buy over here, and sell over here
257.385 -> So in space, it should be stored that what can be the maximum ahead
261.398 -> What maximum value can be ahead
263.157 -> If we can know that first only, then we can take a very smart decision
267.549 -> How we will know that?
268.379 -> Suppose, you made one auxiliary array, right?
270.163 -> We will name it aux, and we will do some pre-processing in this
274.722 -> What is that? we will store the maximum value in this
280.892 -> So, from 5 to ahead, what is the maximum value?
284.288 -> So it can be 5, right?
285.08 -> Because there is nothing ahead of 5
286.956 -> So, from 5 to ahead, 5 is the maximum value
289.256 -> What is the maximum value in 2 and 5?
290.987 -> In 2 and 5, 5 is greater
294.361 -> Then in 7 to 5, which is greater? obviously 7 is greater, right?
298.15 -> So how am I calculating this?
299.737 -> I am calculating this by, current number and maximum so far, previous maximum
304.57 -> From both of them whichever is greater, that will be my answer, right?
306.715 -> So, in 7 and 5 which is greater, 7 is greater
309.026 -> Then in 8 and 7, which one is greater? 8 is greater
311.264 -> So 8 will go over here
312.609 -> In 4 and 8 which is greater? 8 is greater so 8 will go here
315.812 -> Then 8 will be here, in 3 and 8 which is greater? 8
319.538 -> So this preprocessing I have done and I have made an auxiliary array over here, now with the help of this I can take a smart decision
325.713 -> How? So I will move ahead from here, one by one
329.143 -> So first I came to this stock, stock price
331.902 -> So over here I saw it is 3, so what maximum can I get ahead?
335.808 -> I can see I can get maximum 8
337.595 -> So from here my profit will be 8-3=5
340.637 -> So, I will create a maximum profit, which will finally be my answer
345.805 -> So, I will say ok 8-3=5, so this will be 5
349.98 -> Then, I will come 1 step ahead,and I will check over here, that my price is 1, and maximum I can get is 8
358.044 -> So 8-1=7, so I can get 7, if I purchased it on day with 1 price
361.945 -> And 7 price is greater than maxprofit, we will update maxprofit=7
368.889 -> Then we will move ahead like this only, then 8-4=4, 4 is not greater than 7, so still 7 is greater
375.53 -> 8-8=0, so there is no benefit
378.183 -> 7-7, no profit
379.521 -> 5-2=3, it is not greater, and there is nothing greater even ahead, so our answer is 7
385.456 -> So over here, we have used a very simple technique
388.286 -> We have used space over here, and due to which this gets solved in O(n)
393.625 -> So, over here the time complexity is, O(n)
397.915 -> But you will see over here we are using space, we are using auxiliary array, due to which space complexity over here is O(n)
404.729 -> In the above our space complexity was constant
408.024 -> So now we do not have to optimize this further, because this is in the interviews
411.198 -> They will keep on telling you that can still be optimized or not?
413.967 -> So, now how can we still optimize this?
416.618 -> So, they will say, solve this in linear time complexity and use space as constant
421.438 -> So now, this is the real question, and now in this we will have to think something
426.757 -> We have to think of some trick, some logic
428.958 -> With which this can be solved, and it is nothing more dangerous, it can be solved in a very simple way
433.726 -> Think a bit after that I will tell you
435.353 -> So, if all have thought then very good, but if you could not think then, do not worry, over here a trick will be applied
439.961 -> Basically what we had done in the method before this is we were purchasing it every day and we were seeing what maximum profit can we get in future
446.621 -> What is the maximum price in future?
447.865 -> In this we will do the reverse, we will go the opposite way we will basically see to sell this every day, and we will see what was the minimum price before that
456.723 -> Because suppose I am selling it today, then the minimum price before this, if I had purchased at that then I would have got maximum profit
465.121 -> So I will go on any day, suppose I am going on this day
467.414 -> So if I am selling it on this day, then if I know what was the minimum price before this, which was on this day
473.741 -> Then I know on selling on this day, what maximum profit I can get
477.134 -> It will be 7-1=6
478.711 -> So this in the trick, we have to store minimum price so far at one place
483.797 -> And we have to try to sell everyday
486.102 -> And return the maxprofit finally
488.068 -> So it is very simple
489.235 -> So everyday we will store minimum, the minimum is 3, minSoFar=3
498.025 -> We will move ahead, so now if we will sell on this day then 3-3, profit will be 0
504.714 -> So we will create maxProfit=0, moving ahead now minSoFar=1, because 1
518.14 -> So minSoFar=1,so even if we will try to sell the same day then profit =1-1=0
523.461 -> Now we will move ahead, now we will see what is minimum
527.597 -> So if we have to see minimum for these 3, then minimum from minSoFar and this, so which is smaller in 1 and 4? obviously 1
534.224 -> So there is no need to update minSoFar, we will try to sell on current price
538.906 -> So profit=4-1=3, so this is greater the maxProfit, so maxProfit=3
545.837 -> Means, if we will sell over here at 4, and the minimum before that, which was on this day
549.099 -> If we would have purchased on that day, then the profit would be 3
552.201 -> Now we will move ahead
553.398 -> We will come on this day
554.527 -> So, we came on this day and you can see that, is this less then minSoFar? no
558.969 -> And what is the profit, 8-1=7, and this is greater than maxProfit, so we will update maxProfit=7
566.667 -> Now we will move ahead, we will come on 7
568.585 -> we will check minSoFar=1, and 7-1=6
574.682 -> And we were getting profit of 7, so will not update this fine
577.506 -> Still this will be 7 only
579.056 -> Then this will be 2, the 5 but maxProfit will be 7 only
583.531 -> And we will finally return 7
584.951 -> we are able to get maxProfit with this configuration
587.233 -> You can check this for multiple test cases, but this will be the technique, basically you have to take 2 variable, minSoFar and maxProfit
594.923 -> And our work will be done with this
596.649 -> Over here you can see, there was no need to take any extra space
599.051 -> This is done in constant space
600.552 -> And this is solved in linear time complexity, code is also very simple I will tell you in some time
605.65 -> Then you will understand it more easily
606.935 -> So over here I have coded this and it is very simple by taking 2 variable
610.144 -> maxProfit and minSoFar, and the code is very simple
614.326 -> The logic which I had used same that logic only I have coded over here
616.933 -> We will dry run this, this is our example
619.053 -> And we will dry run in this see what answer is coming
621.648 -> So, we will start from here maxProfit=0, minSoFar=a[0], which is 5
631.345 -> We will go inside
633.231 -> We are checking minSoFar= math.min(minSoFar, a[i])
637.537 -> So we are starting from 0, so what is smaller in 5 and 5, so here it will come 5
643.726 -> Then we will find the profit, int profit=a[i]-minSoFar, so profit=5-5=0
654.072 -> So what is maxProfit, maxProfit= math.max(maxProfit, profit)
660.669 -> So profit over here is 0, so our maxProfit will be 0
664.052 -> Now we will move on the next day
665.436 -> Where the price is 2
667.182 -> And we will check minSoFar=Math.min(minSoFar, a[i]), which is smaller in 5 and 2? 2 is smaller, so minSoFar=2
678.29 -> Then what is the profit?
680.242 -> profit=a[i]-minSoFar, i.e 2-2=0
684.241 -> So profit=0
686.92 -> maxProfit=0, so now we will move on next day
689.786 -> When the price is 6
691.426 -> Now what is minSoFar is , which is smaller in 2 and 6, 2 is smaller so minSoFar will not be updated
698.018 -> profit=6-2=4
702.966 -> Now we will check for maxProfit, which is greater in current profit and this profit, then which is greater in 0 and 4?
710.222 -> 4 is greater, so maxProfit=4
713.608 -> And we will move ahead
715.214 -> now our day will be 1
716.355 -> The day on which the price is 1
718.242 -> So what is minSoFar is, which is smaller in 2 and 1, 1 is smaller so minSoFar=1
725.474 -> And what is the maxProfit from here? it can be 1-1=0, and 0 is not greater then maxProfit, so we will not update maxProfit
734.373 -> Ok, now we will move on next day, on next day price is 4
737.983 -> so price is 4, minSoFar is, which is smaller 4 and 1? 1 is smaller then it will not be updated
744.172 -> profit=4-1=3
746.962 -> and we will check which is greater in 3 and 4? 4 is greater
749.739 -> So we will say we will not update, maxProfit will be 4 and finally maxProfit will be returned, which is 4
756.364 -> And when this is coming, when we are buying on 2 and selling on 6
760.341 -> We had one more chance to buy, in 1 and 4, but from here our profit would have been 3
764.662 -> So the maxProfit=4 we will return that
767.881 -> And this logic is finished over here
770.501 -> If you will solve with this, then your time complexity is O(n), but space complexity is constant
777.345 -> So this is an ideal solution for this problem
780.037 -> It was this much only, I hope you all have understood this
782.662 -> And with this only, our stock buy and sell no. 1, is finished
786.22 -> After this we will see the second variant where we can buy and sell any number of stocks
790.366 -> That will be a bit different from this, so we will see that in next video
794.269 -> With only I will go, like this video, subscribe the channel
