Community Problem
Minimum Falling Path Sum
Difficulty: Medium
Find the minimum sum of a top-to-bottom path in a square matrix where each step moves to one of three cells directly below, using row-by-row DP.
Minimum Falling Path Sum
Find the minimum sum of a top-to-bottom path in a square matrix where each step moves to one of three cells directly below, using row-by-row DP.
By @averyperry
January 1, 2026
·
Updated May 18, 2026
1,001 views
22
4.3 (10)
I had this on a Datadog onsite and it's a textbook grid-DP, but the framing matters: the natural recurrence walks DOWN the matrix (dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])), and once you see that, the whole O(n^2) solution falls out in ten lines. The catalog covered minimum-path-sum (which only allows down/right) but it skipped the (c-1, c, c+1) falling variant.
Minimum Falling Path Sum
Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.
A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
Examples
Example 1:
- Input:
matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]] - Output:
13 - Explanation: One falling path with minimum sum is
1 -> 4 -> 8. (Or1 -> 5 -> 7for13, or2 -> 5 -> 7for14.)
Example 2:
- Input:
matrix = [[-19, 57], [-40, -5]] - Output:
-59 - Explanation: Path
-19 -> -40sums to-59.
Example 3:
- Input:
matrix = [[7]] - Output:
7 - Explanation: A 1x1 matrix has the trivial path
[7].
Example 4:
- Input:
matrix = [[1, 2, 3], [-100, 100, 100], [100, 100, 100]] - Output:
1 - Explanation: Walk
1 -> -100 -> 100, summing to1. (2 -> -100 -> 100also yields2, but1 -> -100 -> 100wins.)
Constraints
n == matrix.length.n == matrix[i].length.1 <= n <= 100.-100 <= matrix[i][j] <= 100.
Follow-up
Can you solve this in O(n) extra space? Yes. The recurrence only depends on the previous row, so a single rolling array of size n suffices. Either keep two arrays and swap, or do the row update in place from left to right while temporarily saving the old dp[r-1][c] value before overwriting.
Solution
Hints
Solution Walkthrough
Approach: Rolling-Row DP (O(n^2) time, O(n) space)
Let dp[r][c] = minimum falling-path sum ending at cell (r, c). The recurrence:
dp[0][c] = matrix[0][c]
dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])with out-of-bounds neighbors treated as +inf (or simply skipped via boundary checks). The answer is min(dp[n-1][:]).
Key Insight
Each row's DP values depend only on the previous row, so we keep two n-sized arrays (prev and next) and swap. This drops the space from O(n^2) to O(n) without changing time complexity.
Algorithm
- If
n == 0, return 0. - Initialize
prev = matrix[0](a copy). - For
rfrom 1 ton - 1:- For each
cin0..n-1, computebest = min(prev[c-1], prev[c], prev[c+1])with boundary guards. next[c] = matrix[r][c] + best.- Set
prev = next.
- Return
min(prev).
Why It Works
The recurrence is correct because every falling path that ends at (r, c) arrives from exactly one of (r-1, c-1), (r-1, c), or (r-1, c+1). The minimum over those three predecessors plus matrix[r][c] is, by induction, the optimal sum to reach (r, c). The final min over the bottom row picks the optimal endpoint.
Complexity
Grid scan
Time O(n^2) (every cell looks at 3 neighbors, constant)
Space O(n) (one rolling array)Pitfalls
- Indexing
prev[c - 1]whenc == 0(orprev[c + 1]whenc == n - 1). Boundary cells have only 2 candidate predecessors, not 3. Guard withif (c > 0)andif (c < n - 1). - Not copying
matrix[0]for the initialprev. If you aliasmatrix[0], the first row update will silently mutate the input. Useslice()/[:]. - Returning
dp[n - 1][0]instead ofmin(dp[n - 1]). The optimal path can end at any column in the bottom row; the column is a free choice.
Solution Code