DSA problem
Minimum Falling Path Sum
Given an n x n matrix of integers matrix, return the minimum sum of any falling path through it. A falling path starts at any element in the first row and chooses one element from each row. The next row's element must be directly below or diagonally adjacent: from (i, j) you may step to (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
This is a "Triangle"-style DP on a rectangle. Let dp[i][j] be the minimum path sum ending at cell (i, j). The recurrence pulls the minimum from the three valid predecessors in the row above, clamped at the row boundaries:
dp[i][j] = matrix[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]), where out-of-range columns are simply ignored (treated as +∞).
A naive recursion that explores all paths is exponential. Memoization brings it down to O(n^2). The clean bottom-up version walks the rows top-to-bottom while maintaining only the previous row. Because each new cell needs only three contiguous values from the prior row, the DP can be space-optimized to a single 1-D array of length n, with care taken to read the diagonal predecessor before overwriting it.
The final answer is the minimum value in dp after the last row is processed. Total complexity: O(n^2) time and O(n) space.
Examples
matrix = [[2,1,3],[6,5,4],[7,8,9]]13matrix = [[-19,57],[-40,-5]]-59matrix = [[7]]7Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 100
- -100 <= matrix[i][j] <= 100
- A falling path goes from row 0 to row n - 1, one row per step.
- From `(i, j)` the next cell is one of `(i + 1, j - 1)`, `(i + 1, j)`, `(i + 1, j + 1)`.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.