Minimum Falling Path Sum

How it works

If we are allowed to modify the input matrix, we can avoid using any extra space for DP. We update each cell in place to store the minimum path sum to reach that cell. This is the most space-efficient approach, using only O(1) extra space beyond the input.

Steps

1. Start from the second row (index 1).
2. For each cell (r, c):
   • Compute the minimum of the three cells above: (r-1, c-1), (r-1, c), (r-1, c+1) (treating out-of-bounds as infinity).
   • Add this minimum to matrix[r][c].
3. After processing all rows, return the minimum value in the last row.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(1) extra space.

Things to watch for

Out-of-Bounds Column Access

When computing the minimum from the three cells above (left-diagonal, directly above, right-diagonal), forgetting to check column boundaries causes index errors. The leftmost column has no left-diagonal parent, and the rightmost column has no right-diagonal parent. Always handle these edge cases by treating out-of-bounds values as infinity.

Modifying Input While Reading

In the in-place DP approach, you update matrix[r][c] using values from the previous row. Since you read from the same row you just wrote to, there is no conflict. However, if you mistakenly read from cells you have already updated in the current row, you will get incorrect results. Process each row independently from the previous row.

Forgetting to Check All Starting Columns

The path can start from any column in the first row. A common mistake is starting only from column 0 or assuming the minimum value in the first row is the optimal start. You must either try all starting columns explicitly or let the DP naturally propagate all possibilities.

from typing import List

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        N = len(matrix)

        for r in range(1, N):
            for c in range(N):
                mid = matrix[r - 1][c]
                left = matrix[r - 1][c - 1] if c > 0 else float("inf")
                right = matrix[r - 1][c + 1] if c < N - 1 else float("inf")
                matrix[r][c] = matrix[r][c] + min(mid, left, right)

        return min(matrix[-1])

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int N = matrix.size();

        for (int r = 1; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int mid = matrix[r - 1][c];
                int left = (c > 0) ? matrix[r - 1][c - 1] : INT_MAX;
                int right = (c < N - 1) ? matrix[r - 1][c + 1] : INT_MAX;
                matrix[r][c] = matrix[r][c] + min({mid, left, right});
            }
        }

        return *min_element(matrix[N - 1].begin(), matrix[N - 1].end());
    }
};