Minimum Path Sum

[@KevinNaughtonJr]

Dynamic programming questions can be tricky so I hope this explanation made sense!

[@ashutosh.sharma]

Thanks for the great explanation. please make a video on leetcode.com/problems/longest-univalue-path/ sometime in future. Thank you :)

[@chiragchatwani9124]

Hey You make awesome content but can you make a video dedicated on How to use collection framework and all its method I am new to java and its very confusing please. Thanks in advance

[@theb2ube]

Line 10 could be : dp[i][j] = grid[i][j]; to keep it simple.

[@thesudhir9]

I saw many of your videos. Best thing about your solutions are they are very very intuitive. Once you spend 5-10 min on the video, you'll never forget it. Keep making more videos of complex problems. thanks

[@meenameiss]

Definitely went and did it before i watched the video. I did it in space(1) by just reusing the given matrix instead of creating an auxiliary one. (I'm sure you thought of that but wanted to keep it simpler) Thank you for the content, keep going! Maybe next time finish with a follow up with potential improvements even if you don't code them

[@KevinNaughtonJr]

Pedro Silva anytime and good stuff that's an awesome optimization!!! And good idea I'll see what I can do about mentioning potential improvements during vids :)

[@akashrajpurohit97]

Hey Kevin.. Thanks for your amazing videos.. The explanation is very clear and I am just about to finish you 88+ long Playlist of LeetCode questions and in every question I have learned something new which have helped to crack the first interview round of a company that I attented couple of weeks back.. The second round is tomorrow and I'm preparing myself by going over your Playlist. Just wanted to say thanks for doing this.. Appreciate it.

[@KevinNaughtonJr]

Akash Rajpurohit that's awesome Akash and anytime I'm happy to hear my vids have been helpful! Good luck with the interview tomorrow and let me know how it goes!!!

[@akashrajpurohit97]

@@KevinNaughtonJr It went awesome.. Was asked one Algorithmic question which I was able to solve in optimized way in around 20 mins.. Rest 45-50 minutes there was discussion and questions based on my resume and projects. The silver lining to it was in the end the interviewer told that he was impressed by my work on side projects and other freelance projects that I do. Will hear from them in about a week's time about the results. Hoping for positive feedback. Solving problems along with you by following your thought process on how to tackle certain types of question truly helped me. You're awesome.. Thanks again✌️

[@hardikshettigar805]

@@akashrajpurohit97 Hey! Curious to hear your journey p:

[@visheshaggarwal3395]

at line 10: dp[i][j]+=grid[i][j] should be dp[i][j]=grid[i][j]; Result will be same in either case as their is nothing in dp[i][j] at start.

[@lugiadark21]

I was confused on why he used +=, thanks for the clarification

[@WarrenMoofett]

Thank you so much for this! This came up in 30day leetcode challenge and I was having trouble as I was trying to implement priority queue but dp made it so much simpler

[@devanshmaurya9928]

Yo bro, I also came here because of the Leetcode challenge. Although I implemented it using DFS and I was getting TLE for larger inputs

[@FernandoTakeshiSato]

I went ahead and attempted a graph search, only to have the tests blow up with time limit exceeded - I even added some optimizations, but no cigar. In this particular case, it seems like DP is the way to go. Anyway, one potential optimization (aside from reusing the provided grid), is iterating through the first row and first columns in their entirety first, so when you go into the double fors, you start fom 1 instead of 0 and there's no need to check the indexes. This way you eliminate the if statements, at the price of splitting up the code a bit. I think runtime will be the same, since you're not double checking / calculating anything. Anyways, thanks for the videos man. I've got on site interviews with Amazon coming up and am running through the videos you marked as questions they asked, so I can kind of focus my studies a bit. Cheers!

[@darshantsdarshan1]

Fernando Takeshi Sato great efforts!

[@sateeshtata]

Nice explanation. Thank you for discussing the SC and TC at the end :)

[@KevinNaughtonJr]

Sateesh Tata anytime and thanks Sateesh!

[@ChocolateMilkCultLeader]

Rips off shirt and dances when Kevin solves problem

[@100bands]

I got confused when I saw the inner loop going from 0 - dp[i].length It works fine with dp[0].length and it's less confusing. The arrays will all have the same length anyway. So this is fine: for(int i = 0; i < dp.length; i++){ for(int j = 0; j < dp[0].length; j++){ ......... } }

[@athenanouhi]

@Kevin , Thanks for the video. How about if the question is finding the actual paths that lead to the minimum sum? So instead of returning the minimum sum value, we should return all those paths (vector). This is an interview question and has been puzzling me.

[@amaleldick9899]

Hey Kevin! Really love your videos - I've been struggling with understanding Longest Palindromic Substring for a while now, could you solve it sometime?

[@nash_tech]

Thank you for the explanation. Very clear instruction and implementation.

[@goodwish1543]

Straight to the point. Good job.

[@KevinNaughtonJr]

Good Wish thanks!

[@sanyamgoel1259]

Can you please make a list of questions asked in Amazon of leet code premium . Because some of the students are not comes such background that buy a premium account. Looking positive response from your side. Thank you.

[@jlecampana]

AWESOOOOME!!!!! I love the DP Videos! Thank you Kevin Naughton Jr.

[@KevinNaughtonJr]

jlstr anytime!!! Glad you enjoyed :)

[@vernon_4411]

For clarification, the code between line 10 and line 17 can be rerrangened by using assigment insteadl of adding, dp[i][j] = ... + grid[i][j];

[@OverLordOfDa3rdWorld]

Dude, I love this solution! It seems so intuitive now, wow!

[@KevinNaughtonJr]

thanks!

[@umabharati9911]

Hi Kevin, That's a good explanation. Is it possible to do it in the DFS method? Would you please tell me where am I going wrong in the below code? public static int minPathSum(int[][] grid) { int row = grid.length; int col = grid[0].length; return findMinPath(row,col,0,0,grid,0); } public static int findMinPath(int row, int col,int i, int j,int[][] grid,int sum){ if(i= row || j=col ) return 0; sum +=grid[i][j]; if((i == row-1 && j==col-1)) return sum; int x = findMinPath(row,col,i+1,j,grid,sum); int y = findMinPath(row,col,i,j+1,grid,sum); return Math.min(x,y); } I am waiting for your response. Please help me out. Thank you!

[@chiragchatwani9124]

Hey You make awesome content but can you make a video dedicated on How to use collection framework and all its method I am new to java and its very confusing please. Thanks in advance

[@anushree3744]

Hi Kevin, thanks for your effort. Really helpful. One request though, could you please spend some time on your thought process while coming to the optimal solution/algorithm from brute force approach? this will really help us. Like for this problem, my first thought was backtracking, as at each point, we have two choices, either go right or down. if the chosen one does not lead to min cost then backtrack and select the other choice and see if it yields min cost.

[@leroyhutchinson4497]

Honestly the thought process for algo questions is something that will come with time the more experience you have, the more questions you do that are similar to this one youll build a habit of doing it a specific way.

[@subhabera5775]

Thanks Kevin, quite simple and elegant solution :)

[@manaals6566]

Thank you so much! Literally the best explanations ever for leetcode :D

[@dipukrishnan6383]

Can you suggest one good book on data structures and algorithms? I have searched on internet and find like so many books and it's really confusing. If you can suggest one book which is going to cover everything and can be used as a good reference for preparing for coding interviews then that will be great. And if that book is written for c++, then that's even better.

[@pqrabcd]

Why does this need DP? Can it not be done using BFS with min-heap to give shortest next index? Is it not similar to Dijkstra's shortest path algorithm?

[@tonyconor681]

memorization makes world easy 🌀🌀🌀😍

[@theunknownguy354]

really awesome one thank you!

[@harinijeyaraman8789]

Could you please please make a playlist for DP ? I'm struggling with DP and would love it if you could solve many more DP problems starting from easy to hard problems

[@BookWormsOriginal]

Nice explanation, keep on posting new questions!

[@santhiyanaga]

Thanks!

[@KevinNaughtonJr]

thank YOU i really appreciate it! :)

[@navneetrabadiya7776]

We can use the same matrix passed in input param as our DP matrix, no need of extra memory.

[@sojoru]

I don't know how well you will take my comment but I just want to say that I tried to watch this video over again just to understand the process but I couldn't even get one thing. I get how to solve it but nothing else. I came to this video so I could have some visualization but you just went through everything without even pointing to or giving any visualization of what you were talking about. And the only visualization I receive was you typing the code which wasn't that helpful. You don't have to change anything just saying what I thought. Thanks again for the video.

[@AtoZ-jv1py]

i was struggling from 10 days & u did in 8 min. only (nice)

[@faraz7409]

Another great Vid - Thanks Kevin!!!

[@KevinNaughtonJr]

Faraz thanks Faraz I hope you enjoyed it!

[@dipakraut6058]

Great Explanation, Keep it up Buddy🤑

[@nidhimittal8929]

What is the use of += at line no 10. there will not be any value in dp[i][j] to add with.

[@sureshgarine]

Thank you Kevin, nice explanation :)

[@channeltastypizza]

bless your solution. godsend

[@supremoluminary]

I don't understand the question. How can I understand the question? What questions should I ask?

[@AolaDIY]

Really good explanation!

[@KevinNaughtonJr]

thanks!!!!

[@tianyangren]

My friend gets asked this question, but it needs to output the actual path. Any thoughts?

[@krupapatel4623]

Hi Kevin, can I have solution in Php please ?

[@Krishna42570]

Pls increase rate of uploading videos per dayyyy.....

[@KevinNaughtonJr]

Jonnalagadda Gopi krishna haha I'll try to churn out vids more often but no promises yet :)

[@praphulyadav5065]

sir u made it so easy to understand

[@triplestrikee875]

Great explanation

[@siddhantdubey623]

I used the recursive approach, getting WA for some test cases, can anyone spot my mistake: class Solution { public int minPathSum(int[][] grid) { int row=grid.length-1; int col =grid[0].length-1; int sum = grid[row][col]; int path =findpath(row,col,sum,grid); return path; } public int findpath(int row,int col,int sum,int[][] grid){ if(row

[@kamalhm-dev]

Questions like these really need some visual explanation

[@KevinNaughtonJr]

Kamal Mahmud yeah that's a good idea maybe I can try and add some visuals

[@martialcoder]

Hot to sell t shirt which you have added?

[@rakshith3547]

Hey Kev.. you are awesome bro..but 1 suggestion would be to trace the problem by taking an example which would be more effective to understand.

[@KevinNaughtonJr]

Thanks for the suggestion Rakshit, I'll see if I can do that in future vids!

[@codearabawy]

Thanks, Kevin!

[@akshatdhiman8819]

you r simply awesome my friend

[@Dan-tg3gs]

you could've done that problem without making a copy of the matrix.

[@chiragchatwani9124]

WOW MAN GREAT STUFF

[@KevinNaughtonJr]

Chirag Chatwani THANKS CHIRAG!!!

[@chiragchatwani9124]

@@KevinNaughtonJr Hey You make awesome content but can you make a video dedicated on How to use collection framework and all its method I am new to java and its very confusing please. Thanks in advance

[@shivamshah431]

Why not add the values in place?

[@farukarshad]

what about BFS?

[@amateursoundz6262]

Let's goooo now I understand dp!

[@alvxlopez]

Thank you

[@rajenshrestha8795]

Thanks!

[@AmarjotBhullar]

Thanks a lot man!

[@jamesnguyen5810]

thanks dude

[@KevinNaughtonJr]

Anytime dude

[@shivamtyagi9936]

I came here to seee how to retrieve dat path from where i got the ans🙁 Anyways Ur explanation is gud

[@nizarkadri3109]

Am I the only one who did not understood the solution

[@MK-xl5yo]

im sure before video you solved it many times or watched in discussion panel for possible solution.. way better to see process how you came to this solution, not straight forward solution you just memorized.

[@bee.g.s.ashuwin215]

Awesome explanation!