@3:50 I stopped the video here and went to solve leetcode 931 (nicely done in one go) and leetcode 1014 as well (realized I solved it earlier). I got some ideas to handle now 1937 but still in a little muddle.
Thank you so much! It is a great explanation, sir, definitely I am gonna share this video and channel with all my friends to watch, it is really helpful. please solve the problems consistently, definitely, it will help lots of people and this channel definitely gonna rock
Its simple : the state is : --> dp[i-1][k] - k so when k == m-1 we will have --> dp[i-1][m-1] - (m-1) we simply replace k with m-1. because the last column is denoted by m-1
Many people like me come on UA-cam, post leetcode contest to help themselves upsolve the unsolved problems. So if you could make videos of all 4 problems after every contest that would be of great help. Thanks brother for such a great explanation.
Correct we have to do it for all values of k. and what does k signify?? Case 1 : j > k so k = ( 0,1,.... j-2 , j-1 ) Case 2 : j < k so k = ( j+1 , j+2 ..... m-1 ) So k is the number of columns we have. So for each row we simply precompute the leftPrefixMaximum for all values of `k`. And the rightSuffixmaximum for all values of `k`. Finally we calculate the best answer for all current row. Hence time complexity = O( n * ( m + m + m ) ) ~ O ( n*m ) Let me know if you have any doubts Solution for reference : github.com/Sandip-Jana/UA-cam/blob/main/Leetcode1937.java
Sorry but I didn't understand the problem still based on your explanation. It focused too much on the notations but should've done a walkthrough with the logic directly per iteration
I really like how you explained the question using Leetcode 931 and 1014 as support to explain 1937. Thanks for the video!
Glad it was helpful!
Thanks for explaining by connecting 3 problems. Awesome content🔥🔥🔥
@3:50 I stopped the video here and went to solve leetcode 931 (nicely done in one go) and leetcode 1014 as well (realized I solved it earlier). I got some ideas to handle now 1937 but still in a little muddle.
Ok thanks for feedback. So where exactly do you have doubts? Which part of the problem you didn't understand?
@@sandip_jana link not working
Hi. Yes it wont work. let me know if you have any specific doubts. i will try to answer them here
github.com/Sandip-Jana/UA-cam/blob/main/MaximumNumberOfPointsWithCost.txt
one shot, three problems...good approach
if it is abs diff. then it will always return a positive value then why j< k or j>k matters?
Thank you so much! It is a great explanation, sir, definitely I am gonna share this video and channel with all my friends to watch, it is really helpful. please solve the problems consistently, definitely, it will help lots of people and this channel definitely gonna rock
great explanation. Keep up with the good work
Such a great way to tackle DP write mathematical equations and then break it apart.
Could you potentially explain how you got case 2 : -j < k? Like why is it -j?
No No. I wrote it as
Case 2 :- j < k
Its not -j haha sorry for the trouble :)
Thanks man. I like the way you explained.
Nice Explanation, thanks
NICE SUPER EXCELLENT MOTIVATED
hey can u optimize memiozed approach code attach below
class Solution {
Long dp[][];
public long maxPoints(int[][] mat) {
long max=0;
dp=new Long[mat.length][mat[0].length];
for(int j=0;j
Great Explanation, thank you
Your welcome :)
Very good explanation. Thank you
Welcome
Nice explanation.........thanks for the video...
Thanks. Really good explanation. My question is how am I meant to come up with these math equations if I haven't seen the question before
Good question! Actually this comes with practice . the more problems we solve the better we become
Can you please explain
rightMax[m-1] = dp[i-1][m-1] - (m-1);
Why do we take -(m+1) part in your code?
Its simple :
the state is :
--> dp[i-1][k] - k
so when k == m-1
we will have
--> dp[i-1][m-1] - (m-1)
we simply replace k with m-1. because the last column is denoted by m-1
Many people like me come on UA-cam, post leetcode contest to help themselves upsolve the unsolved problems. So if you could make videos of all 4 problems after every contest that would be of great help. Thanks brother for such a great explanation.
I will try. I am still struggling to explain properly in my videos as evident from the bloopers :D . But yeah i will try :)
Very Nice Explaination ..
Thanks and welcome
very good explanation appreciated
Glad it was helpful!
Came back to it in the morning, I am still failing to understand that how it is O(nm)
Don't we have to do all the values of k
Correct we have to do it for all values of k. and what does k signify??
Case 1 : j > k
so k = ( 0,1,.... j-2 , j-1 )
Case 2 : j < k
so k = ( j+1 , j+2 ..... m-1 )
So k is the number of columns we have.
So for each row we simply precompute the leftPrefixMaximum for all values of `k`.
And the rightSuffixmaximum for all values of `k`.
Finally we calculate the best answer for all current row.
Hence time complexity = O( n * ( m + m + m ) ) ~ O ( n*m )
Let me know if you have any doubts
Solution for reference : github.com/Sandip-Jana/UA-cam/blob/main/Leetcode1937.java
today i solved sightseeing one, got stuck in contest though for this.
todu ho bhai, 15 min teen questions chaap diye!
thanks :)
Very nice explanation thanks a lot !
very good explanation.
what about the case j == k?
it will be 0 anyways. so penalty will be 0
Sorry but I didn't understand the problem still based on your explanation. It focused too much on the notations but should've done a walkthrough with the logic directly per iteration
No worries. I am trying to explain in a better way
Great explanation
Sir, amazing explanation
You are op🎉🎉
nice explanation
Thanks a lot
good
Thanks a lot.
POTD gang?
Sir, Please upload beautiful problems on Dp and please continue teaching on white board. 🙏🙂 I am eagerly waiting... for your upcoming videos on Dp.
Too Great ! XD
best of what? when you explain explain it clearly please
I am trying to improve my explanation. You may try to read other explanations in the discussion forum of problem for better idea. Hope that helps.
💚💚
noice