hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Minimum Falling Path Sum


  • Approach:

    1. We can re-phrase the problem in the following way.

    2. Now, for any single cell (row, col), its falling sum should be the value of (row, col) + minimum of the values of (row+1, col-1), (row+1, col), (row+1, col+1).

    3. We will start working from the 2ⁿᵈ last row of the given grid.

    4. We will try to find out the minimum falling path sum for the current cell on the 2ⁿᵈ last row following the equation stated in Step 3.

    5. The optimal result of the 2ⁿᵈ last row will then help us to find the optimal result of the 3ʳᵈ last row.

    6. The optimal result of the 3ʳᵈ last row will then help us to find the optimal result of the 4ᵗʰ last row and so on.

    7. If we keep going on then, we will have the most minimal result at row 0.

    8. Then we have to find out the minimum among values in row 0 and return it.


  • Time and Space Complexity:

      • Time Complexity: O(N²)

      • Space Complexity: O(1)


Code [C++]

class Solution {

public:

int minFallingPathSum(vector<vector<int>>& matrix) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n = matrix.size(), ans = INT_MAX;

for(int i=n-2; i>=0; i--){

for(int j=0; j<n; j++){

int candidate = matrix[i][j] + matrix[i+1][j];

if((j-1) >= 0){

candidate = min(candidate, matrix[i][j] + matrix[i+1][j-1]);

}

if((j+1)<n){

candidate = min(candidate, matrix[i][j] + matrix[i+1][j+1]);

}

matrix[i][j] = candidate;

}

}


for(int i=0; i<n; i++){

ans = min(ans, matrix[0][i]);

}

return ans;

}

};