Minimum Falling Path Sum

Share

Given n x n integer matrix, return the minimum sum of any falling path through the matrix. A falling path starts at any element in the first row and chooses the element in the next row that is directly below or diagonally adjacent.

Example 1
Input: [[2,1,3],[6,5,4],[7,8,9]] → Output: 13
Example 2
Input: [[-19,57],[-40,-5]] → Output: -59

Solution Approach

DP: for each cell (i,j), the minimum falling path is min of the three cells above it (i-1, j-1), (i-1, j), (i-1, j+1) plus matrix[i][j].

  • Process row by row in-place.
  • For each row i from 1 to n-1:
  • For each col j: matrix[i][j] += min(matrix[i-1][j], matrix[i-1][j-1 if valid], matrix[i-1][j+1 if valid]).
  • Return min of last row.
Java
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int best = matrix[i-1][j];
                if (j > 0) best = Math.min(best, matrix[i-1][j-1]);
                if (j < n-1) best = Math.min(best, matrix[i-1][j+1]);
                matrix[i][j] += best;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int v : matrix[n-1]) min = Math.min(min, v);
        return min;
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(1)