DP 10. Minimum Path Sum in Grid | Asked to me In Microsoft Internship Interview | DP on GRIDS
Vložit
- čas přidán 28. 07. 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/data-structu...
Problem Link: bit.ly/3q5sqfu
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem Minimum Path sum which teaches you about path sum property in grids.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Very helpful series bhaiya
US Bhaiya, Aapka padane ka trika bhut acha lagta h
@@shubhamtanwar679 bhai ye batao why they have returned 1e9, if apane Integer.MAX_VALUE return krte toh ans glat aa rha
@@JitendraKumar-ti6yd max_value k liye long use karna padega is liye integer value le lete h 1e9 means 10^9👍
next videos dekhte rho subset wali problems me ye doubt bataya h
@@shubhamtanwar679 bhaiya link dedo idhar jis problm ki bast kre ho
In The memoization Approach please don't take INT_MAX in the base condition for (i
thanks
@@stite1191 don't mention
But instead of modifying the base case, you can modify the final return statement to return min(up,left)+ a[i][j]
@@parthparmar9798 yeah i also did the same thing
int up = (i > 0) ? arr[i][j] + helper(arr, dp, i - 1, j) : INT_MAX;
int left = (j > 0) ? arr[i][j] + helper(arr, dp, i, j - 1) : INT_MAX; i did like this
The entire process recursion -> memoization -> tabulation -> space optimization is running on my mind all day. I love DP now and all thanks to you :) You are the BEST!!
:)
Same Here, Its like I have unknowingly memorized it ❤
have not watched pass 2:41, just saw the problem, went ahead and tried to solve it on my own.
1) figured recurrsion
2) did memoization
3) did tabulation
4) and even did space optimization
Striver bhai if you need any proof, if whether or not your teachings help students or not, here is this.
I used to skip the problems whenever it had DP in tags. Not anymore. Thank you very much!
Just spread this series, this is what I will expect :)
Hey can you please tell me why in unique grid path we have initializing everytime up=0 left=0 inside 2nd loop before calling up and left . And why not in this minimum path sum in grid
@@hyperme1831
This is too late but..
if you're trying to draw similar lines between this and prev ques doing it this way may help you
int right=1e8 , down=1e8; // so that while finding the min our ans doesn't get affected , if we instead initialise to zero here our actual dp[i][j] value will go wrong
if(i>0) right = grid[i][j] + dp[i-1][j] ;
if(j>0) down = grid[i][j] + dp[i][j-1];
@@hyperme1831 it may be a late reply but the reason is that we need to find the minimum path. if we initilize i = 0 and j = 0. if the left path is invalid ie.. if i
Striver , after watching 7-8 lectures of dp series , before the next vodeo starts , i try and solve the question on my own from what I've learnt and your teaching method is so versatile that every time i get 'all test cases passed' on leetcode, I'm filled with joy. #STRIVEROP #DPOP
Understood so well with your prev lectures that i could solve this ques by myself for damn all 4 methods! like i am blown! I am totally new to DP and this man is a gem!.
instead of returning INT_MAX i think the best option is to apply conditions at up and left calls say for up if(M>=1) and for left if(N>=1) it will remove the other base case and also don't forget to initialise the up and left with INT_MAX value
dude I have been going through your DP series. You have literally explained the most difficult topic in interviews on which I've struggled for years in a way that I won't ever forget. Thanks man! ❤
You have taught the DP. 8 lecture so well that I've solved the 9th and 10th qs by my own without seeing your solution.. DIl se Thank you ♥
💡Quick Tip : Instead of adding grid[i][j] while finding minimum, you can first find minimum of dp[i-1][j], dp[i][j-1] and then add grid[i][j]. Because if you get INT_MAX from recursion and then you add grid[i][j] it will become negative and effect the answer.
Great , i was also thinking over this , if we are returning INT_MAX in negative index base case , It is giving me some unexpected answers but if I am giving 1e9 , it is working fine.
Got the problem now ..!
Your videos have been the most useful in dynamic programming so far. I finally understand and I can go to the interview with a smile on my face. Thank you
Striver I tried to solve this alone, and I did!! I am soo happy you are my first mentor to teach me DP.
Instead of returning MAX value if(i
Even though solving before the question before watching the video, i still watch the whole lecture. And everytime i feel i have learnt something new. You have done amazing sir. 😍
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
I can't believe that I have solve that problem by myself this is only possible because of u. You teach so so well... Thanks a ton!!
Can't express in words how much you helped me
understood very well
please upload videos daily on regular time we know its hard for you but if possible please consider this.
understood !! Getting better at Dp day by day 😁
You have taught the last two lectures so well that i have solved this problem in all the three ways by myself ! And when i was able to do that i could not beilieve myself that i did it! You are an awsome teacher !
Just saw Unique Path and was able to solve this and last lecture's problem by myself, Thank You so so so so much for explaining with such clear logics. Understood and Thank You Striver.
*Understood*
I also have to say I did this problem with 0(1) space complexity all by my own all thanx to the way you optimize it at the end I got an idea of not just how to solve it via recursion and then convert it to dp, but also optimized the space.
Ik I am late by few months but won't go without completing the full playlist.
O(1) ? But how max I can do is O(m) even with space optimization.
@@mradulchourasiya3868 No new trick. Just modify the original matrix itself to store the DP values. But as it modifies the original, not recommended.
#include
int minSumPath(vector &grid) {
int m=grid.size(), n=grid[0].size();
for(int j=1;j
I think we can use dijkstra's algo with some modification. It will work fine imo. Though im not sure about how optimal it will be but it can find the answer for sure.
Yes i was thinking the same
can also be done by greedily -> using dijkstra for matrix slightly modification
Thank you for this clear and thorough explanation. I finally start to understand DP.
qoute by striver maheswari - "Today's decision might effect you tomorrow"😂 , jokes apart very good series on DP
Underrated comment
UnderStood
anyone following the series properly can solve this question by himself
I am able to the space optimisation myself which i thought was beyond my league such is the level of this guy's teaching.❤️🙌💕
Excellent job man, really loved your work on DP and without doubt best so far on youtube. Keep it up 🔥🔥🔥
Thank you so much Striver for this playlist. Much appreciated!!
I have a doubt
While doing boundary check if we return Integer_MAX_VALUE to get this path eliminated then just by adding something to it, it goes into negative. This is the obvious, as we are adding each cell value. Rather if we take some random big number that is enough to clear all test cases but how can we be sure that path sum will always be smaller, There is very very less probability that it may fail. Is there any way to prevent this?
I think instead of adding the returned value at line 4 and 5 directly.. We can first check min values among them and while returning it from the function we can do g[m][n] + max(left, right).. This way, we are not adding any extra value to left or right so it should work fine even if we take INT_MAX.
you can return -1 and if you get -1 don't add it to your solution .
Do check the constraints
@@saurabhraj201 was looking for this, btw we had to take minimum not max
@@sagarchawla4926 we can do this :
int minPathSum(vector& grid) {
int m = grid.size();
int n = grid[0].size();
vector dp(n, -1);
for (int i = 0; i < m; i++)
{
vector temp(n);
for (int j = 0; j < n; j++)
{
if(i==0 && j==0) temp[j] = grid[i][j];
else{
int up = INT_MAX, left = INT_MAX;
if (i > 0)
up = grid[i][j] + dp[j];
if (j > 0)
left = grid[i][j] + temp[j - 1];
temp[j] = min(up, left);
}
}
dp=temp;
}
return dp[n-1];
}
in space optimize solution, one array(length m) and one variable would be enough to solve it. we could avoid taking two arrays.
how ?
i dont think that approach will work, you will be needing to save the current row in an array for when we move to the next row. Single variable wont work.
@@kv5204 actually it is possible
int n = grid.size();
int m = grid[0].size();
vector prev_row(m, 0);
for(int i = 0; i < n; i++)
{
int curr_row = 0;
for(int j = 0; j < m; j++)
{
if(i == 0 && j == 0) curr_row = prev_row[j] = grid[i][j];
else{
int up = 1e9, left = 1e9;
if(i > 0) up = grid[i][j] + prev_row[j];
if(j > 0) left = grid[i][j] + curr_row;
curr_row = prev_row[j] = min(up, left);
}
}
}
return prev_row[m-1];
We can also solve this problem without using any array or any variable, in O(1) space complexity.
int n = grid.size();
int m = grid[0].size();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(i == 0 && j == 0) continue;
else{
if(i == 0 && j > 0) grid[i][j] += grid[i][j-1];
else if(j == 0 && i > 0) grid[i][j] += grid[i-1][j];
else grid[i][j] += min(grid[i][j-1], grid[i-1][j]);
}
}
}
return grid[n-1][m-1];
Hey man, I was struggling a lot since last 2 years. Your videos are just awesome. I am gaining a lot of confidence in dp. Thanks to you!!!. God bless you
Understood,thank you striver because of your teaching style I'm able to solve by myself
understood sir !!! I Think at 01:30,matrix final index should be (1,2).
And You gave the Ninja Training's problem link not minimum path sum In Grid
Hello Striver - Can we also do all these grid question using dfs ?
The recursion is in a way dfs only
i guess yes
Striver , after watching 7-8 lectures of dp series , before the next vodeo starts , i try and solve the question on my own from what I've learnt and your teaching method is so versatile that every time i get 'all test cases passed' on leetcode, I'm filled with joy
after watching these dp videos, now solving dp problems is solving two sum problem. really easy in one go its accepted each step running in my mind thank you so much striver.
striver please try to complete it fast our Placements are near
its not enough that I succeed, others should fail too !
I have understood but because of the last two lectures, I was able to solve this problem in all the three ways all by myself. Gaining some confidence now...
Understood it clearly. Thank you so much.
i'm able to do this question in O(1) space , just modifying the input array :
public int minPathSum(int[][] grid) {
int m=grid.length,n=grid[0].length;
for(int i=0; i0) grid[i][j]+=grid[i-1][j];
else {
grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
}
}
}
return grid[m-1][n-1];
}
ThankU So Much Bhaiya ❤️
yes bro we can do this things in other previous code as well
never do this in an interview, you're not supposed to modify the input parameters
I did the question in 2 minutes, without even looking at your solution. You teach very well.
Understood and also gained more confidence.
thank you striver❤❤
Playlist is just amazing. Thank you Striver. "Understood". ❤
Happy to solve this question before seeing the video...i even had different base cases (like u went from bottom to top but i did in opposite order) thanks striver
Understood. Thanks for creating the playlist.
did this one only using previously taught concepts, awsome teaching bro. appreciate the efforts.
bro you are so so good at teaching, i just can't express 🔥🔥🔥. Keep growing, our support is with you. And at last UNDERSTOOD
i am addicted to your lecture just because in every lecture i am learning something new.
Understood!! even tried it myself after watching previous lectures!!!!
UNDERSTOOD...!
Thanks striver for the video... :)
UNDERSTOOD and thank you so much for these lectures
Thanks Striver. Understood.
I think for the first time I am able to solve DP problem.
Understood! I appreciate for your explanation!!
Understood, sir. Thank you very much.
now i feel confident in dp and solve question before watching the video
thankyou for providing such a amazing lecture.
Understood!! feeling better than when I started Checkpoint 1
thank you very much sir , For the first time I solved a dp problem by myself after watching your previous videos.
BEST Dp Series to ever come across.
Understood. Superb Explanation.🔥
crystal clear explanation thank you bhaiya :)
Thank you so much! Did this on my own. Just came here to verify :)
loving this series!!❤❤❤❤
It's very easy to understood when u watch grid path video
Understood
Waiting for the next lecture!!
Understood bhaiayya... you are making dp easy for me.
previous videos were awesome so ye khud hogya ..thanks habibi
"understood" and thank you bhaiya already feeling confident enough!
Understood pretty well!🙌
understood men...thank you so muchhhhh
Great explanation, thank you.
Understood!! The best series for DP so far on youtube. You r the best Striver bhaiya providing such classy content at 0 fees. Thank u bhaiya for this amazing series..
Understood. Crystal Clear
I Simply Loved It 😍. Thanks Striver🥰
Understood, bro you are a GOAT teacher man!
understood sir ji
such crystal clear explanation 🤩🤩
this booooooms my mind as it can solid take an hour and half or more
done my myself thanks man love u
understood.. Thank you
Amazing charisma, "understood" from my side.
UNDERSTOOD! THANK YOU 🙌
Thank you sir 😁
Understood!
Understood sir thankyou for this great lecture.
understood
Thank You :)
Done ,was busy few days...but i am back !!
understood. Thank you so much.
understood this is awesome!!!
these videos are really worthy
Thanks for this!!!
Understood Sir Thank you very much
Thanks buddy, I was able to do it by myself❤
Understood. Thankyou sir
Now I can say...I LOVE DP 💕💕
FYI - this can be done in-place by editing the matrix
def f(m,n,grid):
# inplace
for i in range(1,m): grid[i][0]+=grid[i-1][0]
for i in range(1,n): grid[0][i]+=grid[0][i-1]
for i in range(1,m):
for j in range(1,n): grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
return grid[m-1][n-1]
Understood 😊 Thank you
Wanna learn dp..just go too takeuforward dp playlist..
Thank you Bhaiya ❤️ for such a wonderful playlist..
By watching your lecture 8, I was able to solve both L9 and L10 problem. So really, Thank you.
very well explained. Thanks for the content. US :)
Understood bhaiya,,, thanks for your efforts.
Understood...Thank you!!!