Minimum path sum | Min cost Path | Dynamic programming | Leetcode #64

This video explains a very important programming interview question which is to find minimum cost path or minimum path sum. I have shown backtracking method along with memoization optimization and finally explained the most optimal dynamic programming solution using proper example. Finally, i have explained the DP code and CODE LINK is present below. This is the 64th number question from LEETCODE. 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/...

[@codestorywithMIK]

Explaining things like "Why won't Greedy work here", then going from "recursive" approach to optimized DP approach. This is how everyone wants to see a problem and this is how everyone should look at a problem. Start from worst and make improvements step by step. This makes your teaching style special. Thanks

[@techdose4u]

Welcome :)

[@junelcjun]

i agree. this is one of the best videos.

[@ismail8973]

That's makes sense

[@debaratighatak2211]

well said! I agree

[@GodOfFaith]

Just in 14 mins

[@CostaKazistov]

Clearest explanation of 3 different approaches to solving Minimum Path Sum problem 💯

[@zelo_s6707]

Thanks for this approach! Using the greedy and recursive approaches helped me understand why one would use the DP method. Nothing else made sense up until now. Keep it up!

[@anushreegupta5830]

Hats off to your teaching style! Legit the best explaination.

[@ronaldabellano5643]

The best. I like the use of colors that made it easy to follow.

[@techdose4u]

Thanks :)

[@ismail8973]

Explanation for Why greedy algorithm doesn't work was top notch. people usually doesn't try to think or explain in that angle. Thanks

[@khan.mansoor]

You explain both problem and solutions very well. Commenting for expressing gratitude as well to offer support. Please keep up the good work.

[@peter-eh2oq]

Thanks! Please keep going!!! Thanks soooooooooo much!!! I saw a lot of vedio about this question, you have the best explination.

[@genvalencia1740]

I come here whenever I start to feel anxious about my solution not panning out, and I'm solving in Python. :) Thanks again for these walk-throughs, they really help. =D

[@techdose4u]

Welcome :)

[@prafulparashar9849]

Great explanation !!
The steps which we followed were the exact steps and approaches which came to my mind while looking at this problem for the very first time.
I was able to go till recursion(backtracking) approach but could not figure out the last one.
Thanks !! This was helpful.

[@Dizzydizzydizzy7]

Literally best explaination on youtube

[@prathamkesarkar]

As usual sir I was able to solve this within minutes with your explanation.

[@PriyanshuKumar-om8np]

The best explanation I have ever seen.

[@fussycat2798]

Nicely explained the concept. Really like it. I was able to solve the similar problems in less time. Thanks a lot for the detailed explanation

[@Noizept]

The best video i found so far to explain this problem.

[@techdose4u]

Thanks bro

[@alfredomora5555]

I just had an assessment wish I saw this video earlier. The question was very similar. I appreciate your content thank you!

[@techdose4u]

Thanks 😊

[@InsightWeaver]

Amazing video mate! explained thoroughly. Cheers

[@UJJWALGIRIRA]

bhai op zeher explaination🔥🔥🔥🔥🔥🔥🔥

[@techwithlord]

This is a best ever video I have ever seen from this only one video I clearly understand the GREEDY, RECURSION AND BACKTRACKING also hats off dude to your work

[@techdose4u]

Thanks 😊

[@dileepkumar-nd1fo]

You are mastered in explaining the things man.
Such a neat explanation with clear voice and the colour combination will make us remember easy.

[@techdose4u]

Great :)

[@utkarsh5165]

Wonderful Explanation BY Tech Dost.. (Dosh)

[@debaratighatak2211]

Another amazing explanation, I can't really thank you enough sir! I :) The bright colours in the video really helps a lot too

[@techdose4u]

Thanks 😊

[@OP-yw3ws]

Amazing you solved all my doubts

[@HariPrasad-ox5ri]

Thank you for the simple and elegant explanation!

[@techdose4u]

Welcome :)

[@neharikakhera6411]

Thank you so much for great explanation!!

[@techdose4u]

Welcome :)

[@shreelakshmi6890]

Great Explanation!

[@ABHISHEK-fy1in]

Very well explained. 👌

[@ayoubdkhissi]

this explanation couldn't be better!! thanks

[@techdose4u]

Welcome :)

[@HimanshuKumar-sl6ud]

the way you explain complex things in easy way is awesome. please make more problems solution of leetcode .

[@techdose4u]

Sure :)

[@simon7671]

you help me a lot! I am a beginnner and this question is just too hard for me. After watching your video, i am able to finish a similar question by myself!

[@techdose4u]

Great :)

[@indsonusharma]

i did by marking technique (iterative) like if you have not encountered then add that state and mark it but if you have encountered that (check by using mark 2d array )state before then take minimum of previous and current state(bit mathematical) that also lead me to AC but thanks for this beautiful approach bro! today the base case could'nt stop us in the first go lol!!

[@techdose4u]

This concept is same as memoization. Today I already wrote the base case 🤣

[@AltafHussain-on2oe]

I am falling in love with your Explanation 💖

[@techdose4u]

😀

[@PiyushKumar-ey7qw]

memoization approach did work like a charm, instead of a 2D array, I have used unordered_map where key was a pair of i,j value.
It got accepted.

[@techdose4u]

Share your code bro :)

[@Safar_Ayushi_Ka]

Hey Piyush Share your code

[@divanshuagarwal8236]

Can you please share your code?

[@Amitkumar-nw5mt]

using map insted to 2-d arr wont work

[@sunyulhossen]

@@Amitkumar-nw5mt It will definitely work

[@AnshumanSharmadev]

Amazing!! You made it look so simple! Liked and Subscribed!

[@techdose4u]

Thanks :)

[@anandakrishnan2685]

Nice explanation, thanks!

[@openworld7585]

Thank you for awesome explanations of dp table

[@techdose4u]

Welcome :)

[@lashalezhava2313]

Thanks, you explain very well :)

[@techdose4u]

Welcome :)

[@wilfredomartel7781]

Great!

[@viralmehta2542]

Nice video. Covered various approaches here.

[@techdose4u]

Thanks

[@pradeepvdeepu4768]

awesome explanation and smooth ..... ! thanks a lot

[@techdose4u]

Welcome :)

[@imuksd]

Good Explanations!!

[@programmingstuff5741]

Can you post the solutions of Google kickstart Round A and Round B
These are the such good problems to practice

[@prashantagrawal1140]

Brilliant Explaintion techdose

[@techdose4u]

Thanks

[@shivanij3725]

nice explanation about dp table.Thanks

[@techdose4u]

Welcome :)

[@rishabhgoyal8110]

I hope this channel reaches 1m soon!

[@techdose4u]

Thanks for your support 😀

[@Daniel_WR_Hart]

LeetCode only has a bit over 200K users with a contest ranking, so that might take a while

[@Safar_Ayushi_Ka]

Your videos are amazing plz do make more videos on DP ,it would be grateful Thanks

[@techdose4u]

Thanks. Yes I will

[@whiskerAndPetal]

I am stuck with a similar problem which is finding shortest path in 2D matrix from source to target which given in the problem and I have to return all i,j coordinates of the shortest path only. Please help.

[@DrJavyMartinez]

Dude! Your accent is tough, but after watching your video, I feel EXTREMELY comfortable applying minimum and maximum cost sum traversal algorithms through graphs!!

[@techdose4u]

Great :) Sorry for this accent though 😅

[@praveennandham2933]

can we change the same logic ass required
when soure and destination or given??

[@ambujverma9287]

the way you explain things is phenomenal...
thanks a lot

[@techdose4u]

Welcome :)

[@ambujverma9287]

@@techdose4u bhai you work in any MNC or u study in college(iit?)

[@techdose4u]

MNC....

[@ambujverma9287]

@@techdose4u which one.. if you don't mind brother 😅

[@amansarma417]

i did without the dp vector. Since we could just perform modifications on the same given grid matrix.
Space Complexity O(1) :) . I submitted that way

[@techdose4u]

Pleas share your code.

[@prathameshmahankal4180]

Could someone please help me understand how the time complexity for the last solution is O(N^2)?

[@rahulbhangale4656]

greedy works if you properly define dp table. dp[i][j] denotes minimum path sum from (1,1) to (i,j)

[@LovelyMountainGoat-rd7qy]

Thank you😇

[@pallabghosh3840]

can i say the time will be in recursive approach 2^(m*n) in worst case? so we use dp for n^2 time

[@alancabrera7116]

iiuc, the space complexity is O(n). One only needs one vector for the running minimums.

[@techdose4u]

True. 2 maintaining 2 rows is sufficient. This is true for most table type DP programs.

[@rushabhlegion2560]

What is that Fast I/O in C++ line at the top? Is it necessary?

[@miltonrodrigues8417]

Good Explanation!

[@techdose4u]

Thanks

[@sarathgovind.k.k7951]

very good explanation

[@techdose4u]

Thanks :)

[@chelseaip759]

THE BEST TUTORIAL

[@techdose4u]

Thanks 😊

[@lemax2980]

Great sir, as usual😋

[@techdose4u]

Thanks :D

[@nabidhasan9548]

Great explanation brother

[@techdose4u]

Thanks 🙂

[@Somethingsomethinglol]

Excellent!

[@techdose4u]

Thanks :)

[@shaileshhegde9205]

The recursive way is DFS right with directions of right and below

[@RahulKumar-qu1if]

Thank you!🔥

[@techdose4u]

Welcome :)

[@shivanggupta5421]

def findPath(x:int,y:int):
if(x= len(grid) or y=len(grid[0])):
return
right = findPath(x,y+1)
down = findPath(x+1,y)
return min(right,down)+grid[x][y]
I used this method. I know you said recursive method won't work but I tried for my satisfaction. But when compiling it gives error because it isn't able to compare right and left when the boundary check returns null. Can you tell me where am I wrong

[@jatinshrivastava4231]

What should I do if i also have to count the number of paths through which We can reach the minimum cost as there can be more than one such paths?

[@chetanpatteparapu7600]

Top Down approach using backtracking and memoization:
private int[][] memo;
public int minPathSum(int[][] grid) {
if (grid.length < 1)
return 0;
this.memo = new int[grid.length][grid[0].length];
for (int[] row : memo)
Arrays.fill(row, Integer.MAX_VALUE);
return getMinPathSum(grid, 0, 0);
}
private int getMinPathSum(int[][] grid, int row, int column) {
int currentValue = grid[row][column];
if (memo[row][column] != Integer.MAX_VALUE)
return memo[row][column];
else if (row == grid.length - 1 && column == grid[row].length -1)
return currentValue;
else if (row == grid.length - 1)
currentValue += getMinPathSum(grid, row, column + 1);
else if (column == grid[row].length - 1)
currentValue += getMinPathSum(grid, row + 1, column);
else
currentValue += Math.min(getMinPathSum(grid, row, column + 1), getMinPathSum(grid, row + 1, column));
memo[row][column] = currentValue;
return currentValue;
}

[@ritikgandhi3605]

In line 11 of the code ,why did we initialize cols as
int cols=grid[0].size() and not just as grid.size()?

[@techdose4u]

Because the number of cols are same in each row and grid[O] means no of cols. Grid.size means no of rows because it is a 2D matrix.

[@raj.saurabhh]

Can we not use the extra space and use the given table for dp? I mean my testcase is ok but when i submit one solution is wrong

[@blume0f]

awesome sir

[@techdose4u]

Thanks :)

[@mahipalsingh-yo4jt]

great video sir...........:)

[@techdose4u]

Thanks

[@harifrahman8054]

Nice Explanation

[@techdose4u]

Thanks :)

[@sarvagyaiitmadras8727]

if all 4 direction mvement would be allowed then what would be changes, will changes work in it, or completenew approach would be needed ???

[@techdose4u]

Apply Dijkstra.

[@shapedsilver3689]

When he started getting into why greedy algorithms won't work I knew this was legit

[@techdose4u]

:)

[@jaredmomanyi8178]

works like magic

[@techdose4u]

Nice :)

[@subratarudra2745]

Nice explanation sir

[@techdose4u]

Thanks :)

[@mohammedsadiq1567]

Awesome bro!!

[@techdose4u]

Thanks :)

[@hiteshusingh8571]

very nice explanation

[@techdose4u]

Thanks :)

[@jeevanr5814]

Dp approach is not working for some testcase can you please check it

[@jeromealve6321]

I wish this video came out 3 years ago when I took my algorithms class lol

[@techdose4u]

:)

[@lifestoriesfromearth6271]

which tool are you using for whiteboard

[@tekbssync5727]

What a color combination and style of *Leet code* in the thumbnail ? !!!! 😂

[@techdose4u]

😅

[@marvellouschandan]

It was a clickbait actually :D

[@techdose4u]

@@marvellouschandan it wasn't 😂

[@paragroy5359]

Nice explanation sir....but instead of taking an additional dp vector if we do changes in the given grid vector only then it will be o(1) space solution

[@techdose4u]

👍🏼

[@kercat89]

It's so easy to understand and I loved the break down from the simple to sophisticated approach!
I have a question re the recursive solution - why is the complexity O(2^n) and not O(2^(m*n))? if it means that there's 2 options to about each cell..? Thank you

[@techdose4u]

Thanks. Actually our number of steps will always be (m+n) from top left to bottom right. So, you can say time will be 2^(m+n).

[@kercat89]

@@techdose4u That makes sense. Thank you!

[@harshpatel1385]

🔥solution

[@techdose4u]

:)

[@mohitsoni3446]

awesome

[@techdose4u]

Thanks :)

[@yashgoswami5374]

What will be the solution if we allow to move in all 4 directions?

[@alnaifmilon5420]

Thank you

[@techdose4u]

Welcome :)

[@kbhargavi4400]

TQ bro!😃

[@techdose4u]

Welcome :)

[@abdelrhmansayed340]

thanks

[@techdose4u]

Welcome :)

[@akanshagautam9815]

If we can move up, down, left, and right then what changes do we have to make in the code?

[@techdose4u]

Maybe try with Dijkstra graph algorithm.

[@harshitchoukse2602]

Then you need track the path with visited array in order to bypass the cycle.

[@veereshr]

if we can change the input matrix, we can use the same right? memory optimisation?

[@techdose4u]

Yes if the array is mutable

[@amitavamozumder73]

we can also do dijksta here right? the value in each cell can be the edge weight, which is pretty close to the dp solution.

[@techdose4u]

You can

[@amitavamozumder73]

@@techdose4u can you please make a video on myers diff algorithm, (the one used in github file diff), it's not anywhere in youtube,

[@aneeshmv8201]

Memoization of recursive code to remove overlapping sub problem calls, will give O(N*N ) right?

[@techdose4u]

It will depend on no of repeating subproblems. Actually 2^N is a much larger upper bound due to the constraint in movement. But yes, memoization should give approx N^2. But since we are still doing recursion, actual runtime can go much higher than table method if you get large matrix. So, table method is best for larger cases. I hope you got it :)

[@InsightWeaver]

@tech dose what if add diagonal movement to it? how would we solve it then?

[@InsightWeaver]

also in python 3 verson please

[@jameskurakula8560]

@7:38
grid[I][j]+ min( dp[ i-1][j], dp[I][j-1]) , there it was j-2.

[@prodiptamondal1758]

Thanks

[@techdose4u]

Welcome

[@kumaraakash25]

Amazing explanation but why would anyone go with the DP approach if complexity is the same in both recursion and DP both

[@programmingstuff5741]

Can you post videos on segment tree??
Which is very useful for the purpose of comptetive programming

[@techdose4u]

Already done. Search in videos.