Best time to buy and sell stock 2 | Valley peak approach | Leetcode
HTML-код
- Опубликовано: 4 апр 2020
- This video explains a very important problem from april 30 days coding challenge on leetcode which is also important for software company interviews. I have explained the best time to buy and sell stock by using recursion, memoization and the most optimal valley peak approach. The optimal time is just O(N) for this problem in just O(1) extra space. As usual, CODE LINK is given below. 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 :)
CODE LINK: gist.github.com/SuryaPratapK/...
thank you for another qualify video. For sure this is top notch for interview prep! Keep it up!
I liked this particular video because it shows thought process of optimising solutions. Initially, you solved it brute force, then dynamic programming, and then the final solution. Please try to keep all video formats in same way.
Sure
Exactly, I thought the same.
U r making things very easy for us .Thank you
this too can be done with state machine with only two states, in hand and sold. works fine, Thanks for teaching that 👍
I also solved it with the same approach...Happy to see others are also doing it the same way rather than Dynamic programming method which is less intuitive...
True :)
Thank You @TECH DOSE ...you videos are helping a lot in understanding tricky problems
Welcome :)
Thank you very much for this video! It is of huge help!
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [0]*n
for i in range(n-1):
if prices[i]
This is the same logic :)
1 2 99 100, logically max profit will be 100-1= 99, but acc to this code, it will be 2-1 =1and 100-99=1 , profit will be 1+1= 2.
your solution is quite elegant:
Let me explain what i got from your video, We need to find the local minima and where there is local minima we need to buy the stock,and we need to sell the stock at local maxima
Absolutely correct :)
I just saw your video tag,and solved the question in 1 go ,thanks
Nice :)
Idea is really great and explaination is very clear,thank you so much sir🔥
Welcome :)
could you please explain the meaning and significance of the iosbase and cin line a little more, also can we do something equivalent in java ?
I liked the approach though I did it with O(n) extra space in O(n) time using prefix sum....intution was same as yours...Thnx
straightforward ... I like it!
Thanks :)
Thank you so much for a great explaination.
Welcome :)
In last optimal aproch, when input is increasing then sell and buy on the same day
bro while iterating i the condituon should be i
no when i comes at n it will terminate the loop
int Solution::maxProfit(const vector &a){
int n = a.size(), profit=0;
for(int i=0; i
I think your channel will reach more exponential growth in future
Thank you so much for given free education
Welcome :)
Hi tech Dose , I solved this problem here :
int profit = 0;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i + 1] > arr[i]) {
profit += arr[i + 1] - arr[i];
}
}
return profit;
Here as you said selling and buying on the same day will give no profit : he can leverage that. I passed on the test cases with this. Any thoughts?
After completing the video Just saw you discussed the code. In between I also got stuck at 1 2 3 4 5 as i was using approach of arr[i] > arr[i+1]
which failed. But this one worked.
What tool are you using to draw and sketch on screen ?
Great Explanation
Thanks
Just Wow
super explaination ! well done!
Thanks
Valley - Peak approach is really good. I did the same.
Python sol -
sum =0
for i range(len(prices)-1):
sum+=max(prices[ i +1 ]-prices[ i ],0)
return sum
another great video sir...........!
Thanks
Hi sir, please if possible please upload a video on Best Time to Buy and Sell Stock with Transaction Fee(leetcode 714), the way you explain is awesome.
Ok
Is Top down dp working For all test cases?
clare voice ,easy & best explaination
Thanks
Please keep making such videos try to cover every problem from every platform .
Thanks 🙏
@TECH DOSE Can we use Next Greater Element approach to compute this?
Your videos are awesome 👍
Thanks
Thanks great explanation
Welcome
great
In this question can be sell first and then buy on the same day??
for example : 1 2 3 4
day 1 buy
day 2 sales
then again buy on day 2.
then again sale on day 3.
I am not able to understand question clearly , can someone help?
Hey Surya, may I know the name of the application you are using for drawing over the screen and for your tutorials?
Amazing videos .. my favorite channel
Why can't we buy at valley point 1 this is on second day and sell it on 4th day @TECHDOSE
Isnt the valley peak approach actually hill climbing algorithm?
Can anyone give me valley peak approach timelapse
how to handle the case when current and previous values are equal, like an input of 6 values, as 2 2 2 2 2 2 or case like 9 8 1 2 2 3
When values compared are equal then by buying and selling you won't make any profit. So just skip it.
You are awesome :)
Thanks :)
Nice Explanation! Can you also do a video for Buy and Sell stock III, where maximum k transactions are allowed?
I have done part 3. Next I will do part 4.
@@techdose4u Oh Yes! It's there. Thank you.
Bro please upload one more variation of this question : When we can buy or sell almost k times. Your explanations are awesome. Keep it up.
Okay... Will see
From where did you get the ideas to solve the problem? I tried this problem and time complexity is O(n^2)
Actually by good amount of practice, you will start observing some patterns. It will be easier. Your intuition improves with practice. That's all.
This problem has very simple solution.
//[7,1,5,3,6,4]
var maxProfit = function(prices) {
let totalProfit = 0;
for (let p=0; p
Valley peak op
If possible please explain dp solution too
If you find difficulty then ask.
Hello please can you post a code in java
i have one error below:
Line 4: error: cannot find symbol
int n=prices.size();
^
symbol: method size()
location: variable prices of type int[]
Line 6: error: cannot find symbol
for(int i=1;i < prices.size();i++)
^
symbol: method size()
location: variable prices of type int[]
2 errors
class Solution {
public int maxProfit(int[] prices) {
int profit=0;
int n=prices.size();
for(int i=1;i < prices.size();i++)
{
if(prices[i] > prices[i-1])
profit += ( prices[i] - prices[i-1] );
}
return profit;
}
}
The problem is....you need to use prices.length instead of prices.size(). This should solve your issue.
In java :
static int fun(int[] a) {
int profit = 0;
for (int i = 1; i < a.length; i++) {
if (a[i - 1] < a[i]) {
profit += a[i]-a[i-1];
}
}
return profit;
}
Line 4: error: cannot find symbol
int n=prices.length();
^
symbol: method length()
location: variable prices of type int[]
Read this blog: www.geeksforgeeks.org/how-to-determine-length-or-size-of-an-array-in-java/
correction -> int len = price.length
length() is use for string
for array length method is used.
where is the condtion max 2 times selling stock satisfied
eg: 10,100,30,300,60,600
valley peak approach answer is 900(involves 3 transactions)
but real answer would be 830(2 transactions)
pls help
Is the same problem or a different one
You went full nuclear in the start but the solution was actually colt pistol.
When i saw your DP code,i was wondering why would leetcode classify it as easy if code is so long.
😅
Why you use prefix instead of postfix?why you not use "I++" and use "++I"?
🙏🙏🙏🙏🙏
Bhaaiya I study in JU IT 2nd year as you are my senior I wish to know that for cracking internship in amazon, samsung, Microsoft do I will require a project in hand along with strong ds a, os, dbms, oops concept, if yes what type of project can I make in this span of 2 months time, like flutter, web dev, or anything else. Please reply bhaaiya, and Yes I live next to spetstech.
You can contact me anytime on linkedIn. Since you will be applying for internship then any basic project should do. If you are interested in ML then make a handwritten digit recognizer. You can complete this (including reading) in just 1 day. All codes are available online. If you are interested in WebDev then make a website. That will also be counted as project. It doesn't matter what you choose. It will be good if you do something of your interest. Nobody will complain as long as you do something.
What if there are three valleys? example : 100 10 20 5 30 2 70. Your ans will be 103. But as it is atmost two times so ans should be 93. Please explain
int maxProfit(int* prices, int pricesSize)
{
int sum=0;
for(int i=1;iprices[i-1])
{
sum=sum+prices[i]-prices[i-1];
}
}
return sum;
}
work right
It's correct.
You make it so simple. Are you in college or in a corporate?
Corporate.
But there is no condition that I have to sell on the next day itself.. I can buy when it is 1 and sell on 5 for stocks [1,2,3,4,5]. If I sell every stock on 5 then profit is 4+3+2+1 which is 10. Please correct me if wrong.. Thanks in advance!
The constraint is that you need to sell before you buy again
but the problem says that we can buy and sell stock on the same day
we cannot
I understand the logic in this video and others explaining the "k-transactions". But does this actually work? Have you made money on the stcoks this way?
This is not for real life predictions. Use neural network models for better prediction.
Thank you for pointing in the right direction.
The code is not working for the case {10,22,5,75,65,80} The profit is 87 but using valley peak approach is giving 97 . Can you clarify and very nice content I got the direction.
Sir....tcs code vita is near by....can we have an orientation....on that examination??
I will think on having a live stream discussion on this. That will be helpful. When is the date for exam?
@@techdose4u by the end of the june .......sir
If all goes as planned....if postponed....will be in the month of Aug
Well I will do some research and let you know on it. You search for previous year trends and patterns.
Great Video ..an alternate recursive solution approach in python ..Please comment.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l=len(prices)
memo=[-1]*l
def recurse(curr):
if curr>l-2:
return 0
if memo[curr]!=-1:
return memo[curr]
profit=0
if prices[curr+1]-prices[curr]:
profit=max(profit,prices[curr+1]-prices[curr]+recurse(curr+1))
profit=max(profit,recurse(curr+1))
memo[curr]=profit
return profit
return recurse(0)
Can you please make your videos is Java ????????
I will try :)
in*
This approach does not work if you do not sell the stock before you start buying again. You did not mention this is your problem statement.
[5,5,7,8] (Buy at 5 & 5, sell at 7 & 8, MaxProfile=5, Your Solution=3)
[3,2,3,4,5,4] (Buy at 3, 2 & 3, sell at 4, 5 & 4, MaxProfile=5, Your Solution=3)
[2,3,4,5] (Buy at 2 & 3, sell at 4 & 5, MaxProfile=4, Your Solution=3)
There was only 1 stock which you can buy and you cannot buy another one before selling. That is mentioned in problem statement.
Best solution is still O(N)