Minimum Falling Path Sum | Recursion | Memo | Bottom Up | Leetcode 931
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 8th Video of our Playlist "Dynami Programming : Popular Interview Problems".In this video we will try to solve a good and famous interview problem - Minimum Falling Path Sum (Leetcode 931)
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Minimum Falling Path Sum
Company Tags : Google, Microsoft, Amazon, Flipkart, OLA, Goldman Sachs, MakeMyTrip, OYO Rooms, Samsung
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
SImilar Qn : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach 1 Summary : The approach uses a recursive function MFS with memoization to compute the minimum sum by exploring possible paths from the top row to the bottom row of the matrix. The memoization is implemented using a separate 2D vector t to store previously computed results and avoid redundant calculations. The function iterates through neighboring elements in the next row and selects the path with the minimum sum. The main function then iterates over the first row and finds the minimum falling path sum by calling the recursive function for each starting column. The final result represents the minimum sum of a falling path through the matrix.
Approach-2 Summary : The approach utilizes dynamic programming and a bottom-up approach to fill a 2D vector t with the minimum falling path sums for each element in the matrix. The initialization is done for the first row, and subsequent rows are filled by considering the minimum path sum from the previous row. The result is obtained by finding the minimum element in the last row of the matrix t. The solution efficiently computes the minimum falling path sum in a non-recursive manner, using dynamic programming to avoid redundant calculations.
Approach-3 Summary : The approach utilizes a dynamic programming technique with constant space optimization. It maintains a 1D vector prev to store the minimum falling path sum for each column in the previous row. It iterates through the rows, updating the minimum falling path sum for each element in the current row (curr) based on the values in the prev vector. The prev vector is then updated with the values of the curr vector. Finally, the result is obtained by finding the minimum element in the last row of the matrix. The solution efficiently computes the minimum falling path sum with a reduced space complexity compared to a 2D matrix.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Timelines
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear
The explanation & intution is fantastic :) , please make video on how did we think that when should we use dp , recursion etc all these method
Thanks a lot Dilesh.
Sure thing . Soon i will add playlists on concepts like those.
Thanks again ❤️❤️❤️
You are the only person whose even long videos I can sit and watch patiently.
Thanks a lot for this one too
i love how you focus only on intuition. For a beginner like me, i think it's the most important thing
Sir currently my exam is going on but I take time for daily leetcode question because of u . Some day I mis , but try continously.
we can also further optimize the space complexity to O(n), by using 2 arrays. Bcz my next row is depending just on previous row.
Nice explaination btw 🤘
Indeed Pankaj. I have added this approach as well in my Github repo. It’s always good to explore multiple ways to solve. Great.
Thank you ♥️
So much to learn from this single video😊
As always, best solution and best explanation
To avoid TLE in recursion + memo approach avoid using memset use two for loop to initialize the dp
Also dont initialize dp with -1 (look at the constraints).
My Accepted Code :-
class Solution {
public:
int n;
int dp[101][101];
int solve(vector& matrix, int row, int col) {
if (row == n) {
return 0;
}
if (dp[row][col] != 2000) {
return dp[row][col];
}
int right_down = INT_MAX, left_down = INT_MAX;
int down = matrix[row][col] + solve(matrix, row + 1, col);
if (col - 1 >= 0)
left_down = matrix[row][col] + solve(matrix, row + 1, col - 1);
if (col + 1 < n)
right_down = matrix[row][col] + solve(matrix, row + 1, col + 1);
return dp[row][col] = min({down, right_down, left_down});
}
int minFallingPathSum(vector& matrix) {
n = matrix.size();
int result = INT_MAX;
for (int i = 0; i < 101; i++) {
for (int j = 0; j < 101; j++) {
dp[i][j] = 2000;
}
}
for (int j = 0; j < n; j++) {
int a = solve(matrix, 0, j);
result = min(result, a);
}
return result;
}
};
💪
can u send me the tabulation code for this
@@mayank1522 I have not done this question with tabulation method
bhai aapki coding videos netflix se zyada entertaining h maza aagya
Thank you so much 😇🙏❤️
One of the coolest comments I ever got 🤓
doing great work bro :)
Thanks a lot Yash ❤️❤️❤️
bhai best ho yaar best mazaa aa gaya --- Love from maharashtra
It means a lot. Thank you so much. 😇❤️🙏
I applied a dynamic programming solution to solve it, skipping the recursive approach at first. Managed to do it on the first try with the DP solution.
🙌💪👌
hey bro ... loving ur way of explanation. ❤
Thank you so much Saurya ❤️❤️❤️
👌🏻 such a dope explanation with less views. Extremely underrated.
Sir, why greedy approach is working in the second approach? I mean every time , we are taking the smallest value and adding in the current sum. Please Explain. I am confusing in this because in the 1st approach, it is clear that this is DP question but in the second approach it seems like greedy question
Perfect explaination! Thanks bhai🙌
i always search for ur videos.... keep up the great work😊
Thank you so much 😀
you are great - best solution ever
🥳
bhaiya aapki video dekh kr maja aa gya ...please jo similar question hai uske liye bhi video bna do ...mujhe almost ek din sa hogya karte karte usko...solution yaad ho gya hai ...lekin samaj nhi aaya kisi ka youtube pr...(leetcode 1937)
whats your time complexity for recursive + memoization solution ??
Hi Anand, since we are eliminating to visit the already visited states, the time complexity is reduced to O(n*n)
Would be glad to deep dive into it or go for a discussion more on this if required.
@@codestorywithMIK your solve function is taking n*n time and we are looping for first row to find the minimum so time complexity would become O(n*n*n) ? ?
My bad. You are right.
Thanks for correction ❤️❤️❤️
THanks a lot bhaiya the second approach's explanation was best ❤❤
Always welcome 🙏
Thank you Sir! It was the best explanation i got.
So glad to hear that Manash
Thank you ❤️❤️❤️
what is the reason its giving TLE in the 49th test case???
class Solution {
public:
int n;
int t[101][101];
int solve(vector& matrix, int row, int col) {
if (row == n - 1) {
return matrix[row][col];
}
if (t[row][col] != -1) {
return t[row][col];
}
int sum = matrix[row][col];
int minSum = INT_MAX;
if (row + 1 < n && col - 1 >= 0) {
minSum = min(minSum, sum + solve(matrix, row + 1, col - 1));
}
if (row + 1 < n) {
minSum = min(minSum, sum + solve(matrix, row + 1, col));
}
if (row + 1 < n && col + 1 < n) {
minSum = min(minSum, sum + solve(matrix, row + 1, col + 1));
}
return t[row][col] = minSum;
}
int minFallingPathSum(vector& matrix) {
n = matrix.size();
memset(t, -1, sizeof(t));
int row = 0;
int result = 1e9;
for (int col = 0; col < n; col++) {
result = min(result, solve(matrix, row, col));
}
return result;
}
};
Yes first approach now gives TLE. One new large test is added now.
But in interviews, make sure to discuss this approach first.
sure, thanks@@codestorywithMIK
Bottom up kuch aise kiya tha par memoization ke baad bhi last test case mein TLE aa rha hai...
class Solution
{
public://TRIAL
int t[101][101];
int row;
int col;
int solve(int i,int j,vector& matrix)
{
if(i>=row || j>=col || i
You mean Top Down*
. New test case is added.
But there is one way to fix it. Fill all the values in dp array with INT_MAX
Don’t use memset function to initialise the dp array. Do it with for loop.
hi @@codestorywithMIK how this will help? I am trying to figure out
sir you are a gem aapse dp padhne ka bhut mann hai
Thank you so much. Please follow my DP Concepts Playlist where I have started to explain from basics of DP - ua-cam.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html&si=BdXiWDj5yTp82KMY
2ns solution is mind blowing
hello! please explain the Ninja's training question of code studio, ts is variation of falling sum
2nd approach was super good
best explanation hai bhai thanks : - )
Thank you so much 🙏
bhai Hats off You!!!
❤️❤️🙏🙏
sir memo se 49/50 chal rhe TLE aa rha last case me
Yes first approach now gives TLE. One new large test is added now.
But in interviews, make sure to discuss this approach first.
The very first memoization code is failing because of the testcase containing all zeros n it's giving TLE. Could u explain why?
Yes. New test case is added.
But there is one way to fix it. Fill all the values in dp array with INT_MAX
Don’t use memset function to initialise the dp array. Do it with for loop.
@@codestorywithMIK why this didn't give tle?
intution is fantastic
Best channel ever 🎉
Java Code
class Solution {
public int minFallingPathSum(int[][] matrix) {
int max = Integer.MAX_VALUE;
int n = matrix.length;
int dp[][] = new int[n+1][n+1];
for(int i =0;i
recursion se kr rha jaise aap ne bataya hai pr last ke 3 cases me TLE aa raha hai same aap wala hi code hai
Code
Testcase
Testcase
Test Result
All Submissions
Time Limit Exceeded
49 / 52 testcases passed
Last Executed Input
Use Testcase
matrix =
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
View more
Code
C++
class Solution {
public:
int t[101][101];int n;
int solve(vector& matrix,int row,int col,int n)
{
int minsum=INT_MAX;
int sum=matrix[row][col];
if(row==n-1)
{
return matrix[row][col];
}
if(t[row][col]!=-1)
{
return t[row][col];
}
for(int shift=-1;shift=0 && col+shift
same problem
Bhaiya min path sum -2 bhi isske ho jaayega kya??
👌
Nice explaination
I didnt get the complexity of recursion+memoization?
sir please share your leetcode profile
Hi Aksha, you can google me as @Mazhar_MIK Leetcode”
Thanks for watching 😇
🔥++
Awesome 🙌
bhai mere wala tle de raha hai 49th tc pe memo wala code
Yes. New test case is added.
But there is one way to fix it. Fill all the values in dp array with INT_MAX
Don’t use memset function to initialise the dp array. Do it with for loop.
@@codestorywithMIK ya i did the same
Bhai aapka code aakhri test case pe TLE de rha please update
Yes first approach now gives TLE. One new large test is added now.
But in interviews, make sure to discuss this approach first.
@@codestorywithMIK could you update the code for the large test case
Bhai mera memoization wla TLE de rha hai.
code:
class Solution {
public:
int n = 0;
int t[101][101];
int solve(vector& mat, int row, int col)
{
if(row == n-1)
{
return mat[row][col];
}
if(t[row][col] != -1)
return t[row][col];
int sum = mat[row][col];
int minSum = INT_MAX;
if(row+1 < n && col-1 >= 0)
minSum = min(minSum, sum+solve(mat, row+1, col-1));
if(row+1 < n && col < n)
minSum = min(minSum, sum+solve(mat, row+1, col));
if(row+1
pta nhi,mera memoise me tle kyu aa rha hai bar bar
trying 1289. Minimum Falling Path Sum II
1st solution is giving me tle for the last 49th testcase. Is it happening to everyone?
Yes. New test case is added.
But there is one way to fix it. Fill all the values in memoization array with INT_MAX
Can you please try and let me know if it works then.
@@codestorywithMIK no,it's not working
@@anushkathakur6531 don`t use memset for initializing memoization array with INT_MAX . do it using normal 2 for loop
CODE :
class Solution {
public:
int t[101][101];
int n;
int solve(vector& matrix,int r,int c){
int sum=matrix[r][c];
if(r==n-1)
return sum;
if(t[r][c]!=INT_MAX)
return t[r][c];
int minsum=INT_MAX;
if(r+1=0)
minsum=min(minsum,sum+solve(matrix,r+1,c-1));
if(r+1
@@anushkathakur6531 use normal 2 for loop for filling all the values in memoization array with INT_MAX instead of using memset
CPP Code :
class Solution {
public:
int t[101][101];
int n;
int solve(vector& matrix,int r,int c){
int sum=matrix[r][c];
if(r==n-1)
return sum;
if(t[r][c]!=INT_MAX)
return t[r][c];
int minsum=INT_MAX;
if(r+1=0)
minsum=min(minsum,sum+solve(matrix,r+1,c-1));
if(r+1
@@codestorywithMIK Yeah, it can also be solved by initializing the dp array with -101, that is outside the range.
bhaiya phela solution kaam nhi kr rha, time limit exceeded aa rha.. idk why u didn't got the error.
Can you share your code with me ?
Are you using C++ ?
45 out of 49 test cases are passing🥲
Would like to see your code
@codestorywithMIK
Great explanation. Thanks a lot :)
First solution is not working for me also. 49/50 test cases passed. Please find the code here:
class Solution {
public:
int n;
int dp[101][101];
int solve(vector& matrix, int row, int col ){
//Base condition
if(row == n-1){
return matrix[row][col];
}
if(dp[row][col] != -1)
return dp[row][col];
int res = INT_MAX;
int sum = matrix[row][col];
//explore all options in 3 directions
vector arr = {-1, 0, 1};
for(auto shift: arr){
if(row >= 0 && row+1 =0 && col+shift
@@ritupriya607 my code is almost same
I am also getting tle 49/50 testcases :')
O(1) space bhaiya I did
class Solution {
public:
int minFallingPathSum(vector& matrix){
if(matrix.size()==1)
return matrix[0][0];
int n=matrix.size();
for(int i=1;i=0&&j+1=0&&j+1=0&&j-1>=0){
matrix[i][j]+=min(matrix[i-1][j],matrix[i-1][j-1]);
}
}
}
return *min_element(matrix[n-1].begin(),matrix[n-1].end());
}
};
O(1) space
First code is giving TLE
Yes first approach now gives TLE. One new large test is added now.
But in interviews, make sure to discuss this approach first.
Sure bhaiya@@codestorywithMIK
the leetcode link has to be changed
Thank you so much.
Corrected 😇❤️
Bhaiya ye code galat output deraha h i think likha to sab shi h mene🥲
class Solution {
public:
int minFallingPathSum(vector& matrix) {
int n = matrix.size();
vectorcopy(n, vector(n));
//setting the first row of the new matrix
for(int col = 0; col < n; col++){
copy[0][col] = matrix[0][col];
}
for(int row = 1; row < n; row++){
for(int col = 0; col < n; col++){
int a = INT_MAX;
int b = INT_MAX;
if(col-1 >= 0)
a = matrix[row-1][col-1];
if(col+1 < n)
b = matrix[row-1][col+1];
copy[row][col] = matrix[row][col] + min({matrix[row-1][col], a, b});
}
}
//return the min from the last row of copy
int ans = INT_MAX;
int last_row = n-1;
for(int col = 0; col
You are missing [row-1][col]
Check that also.
@@codestorywithMIK khaa pr bhaiyaa🥲, matrix[row-1][col] mene directly min function me daldiya