LeetCode #931 Medium

Minimum Falling Path Sum

Find the minimum sum path falling from the top row to the bottom row, moving straight down or one column diagonally each step.

dynamic-programmingarraymatrix

Open on LeetCode ↗

02

Intuition

💡

The trap is forgetting that the diagonal moves are bounded at the edges. Column 0 has no upper-left parent to fall from, and the last column has no upper-right parent -- an unguarded min() over three fixed parent offsets either reads past the array bounds or, worse, silently wraps around and compares against the wrong side of the row entirely. The fix is to only include parents that actually exist: for column j, gather dp[j] always, dp[j-1] only if j-1 >= 0, and dp[j+1] only if j+1 < n. The invariant: dp[j] after processing row i is the minimum sum of a falling path that ends at column j in row i, built strictly from in-bounds parents in the row above.

03

Approach

1

Seed with the top row

dp starts as a copy of row 0 -- a path of length one that ends at each column simply costs that cell's own value.

2

Fill downward with guarded neighbors

For each row i from 1 to n-1, and each column j, collect the candidate parent values: dp[j] (straight down, always valid), dp[j-1] (only if j > 0), and dp[j+1] (only if j < n-1). Take the minimum of whichever candidates exist and add matrix[i][j].

3

Read the last row

After processing the final row, the answer is the minimum value across that row's dp -- the cheapest path could end at any column.

04

Solution & live demo

python

▶1class Solution:
▶2    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
▶3        n = len(matrix)
▶4        dp = matrix[0][:]
▶5        for i in range(1, n):
▶6            new_dp = [0] * n
▶7            for j in range(n):
▶8                candidates = [dp[j]]
▶9                if j - 1 >= 0:
▶10                    candidates.append(dp[j - 1])
▶11                if j + 1 < n:
▶12                    candidates.append(dp[j + 1])
▶13                new_dp[j] = matrix[i][j] + min(candidates)
▶14            dp = new_dp
▶15        return min(dp)

05

Edge cases

Leftmost column (j = 0)

Only dp[0] and dp[1] are valid parents; dp[-1] is never included.

Rightmost column (j = n-1)

Only dp[n-2] and dp[n-1] are valid parents; dp[n] is never included.

1x1 matrix

The loop over rows never runs; the answer is the single cell's value.

All negative values

min() still correctly finds the most negative total sum with no special handling needed.

06

Complexity

Time

O(n^2)

Space

O(n)

Each of n rows scans its n columns, checking at most three bounded parents per cell.