Minimum Falling Path Sum — Top-Down Grid DP with Three Choices

Problem Statement#

Given an n x n integer matrix matrix, return the minimum sum of a falling path through it.

A falling path starts at any element in the first row and chooses the element in the next row that is in one of three positions: directly below (same column), diagonally below-left (column minus 1), or diagonally below-right (column plus 1).

Example: matrix = [[2,1,3],[6,5,4],[7,8,9]] returns 13. The best path is 1 -> 5 -> 7 (or 1 -> 4 -> 8).

Example: matrix = [[-19,57],[-40,-5]] returns -59. Path: -19 -> -40.

Constraints: 1 is less than or equal to n is less than or equal to 100, with cell values in [-100, 100]. The matrix is square and small enough for an O(n^2) DP.

Why This Problem Matters#

Minimum Falling Path Sum is one of the friendliest grid-DP questions in the FAANG rotation. Amazon, Google, Microsoft, and Bloomberg ask it because it tests three DP fundamentals at once: identifying the state (row, column), recognizing that each cell has up to three predecessors, and choosing whether to compute in place or use auxiliary memory.

It is also a perfect warmup before harder grid DPs like Cherry Pickup, Triangle, and Minimum Falling Path Sum II (which forbids same-column transitions and forces an additional state).

The Core Insight (Recurrence)#

Define dp[i][j] as the minimum falling-path sum ending at cell (i, j). Working top-down:

• Base: dp[0][j] = matrix[0][j] for all j in the first row.
• Transition: dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) where out-of-range neighbors are treated as infinity.

Final answer: min(dp[n-1]) over the last row.

The three predecessors come straight from the problem statement: from (i-1, j-1), (i-1, j), or (i-1, j+1). Only two are valid at the corners.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: solve(i, j) returns the min sum reaching (i, j). Recurse into the three predecessors. Memoize on (i, j) for O(n^2) time and O(n^2) memory plus stack.

Tabulation: allocate dp[n][n], copy the first row, then iterate i = 1 to n-1 and j = 0 to n-1, picking the minimum of up to three predecessors. Return min(dp[n-1]).

Space optimization 1: two rolling rows of length n. Reduces memory to O(n).

Space optimization 2: in-place tabulation. Mutate matrix itself, adding the best predecessor sum to each cell. Memory becomes O(1) extra. Only do this if mutating the input is acceptable — clarify with the interviewer.

You could also pivot to a bottom-up direction (start from the bottom row, walk up), which is a common follow-up that flips the meaning of dp[i][j] to "min sum from (i, j) to the last row." Both directions yield the same answer.

Visual Dry Run (DP Table Trace)#

Trace matrix = [[2,1,3],[6,5,4],[7,8,9]].

Row 0 (base): dp = [[2,1,3], ?, ?].

Row 1:

• (1, 0): predecessors (0, 0)=2 and (0, 1)=1. min = 1. dp[1][0] = 6 + 1 = 7.
• (1, 1): predecessors (0, 0)=2, (0, 1)=1, (0, 2)=3. min = 1. dp[1][1] = 5 + 1 = 6.
• (1, 2): predecessors (0, 1)=1 and (0, 2)=3. min = 1. dp[1][2] = 4 + 1 = 5.

Row 2:

• (2, 0): predecessors (1, 0)=7 and (1, 1)=6. min = 6. dp[2][0] = 7 + 6 = 13.
• (2, 1): predecessors (1, 0)=7, (1, 1)=6, (1, 2)=5. min = 5. dp[2][1] = 8 + 5 = 13.
• (2, 2): predecessors (1, 1)=6 and (1, 2)=5. min = 5. dp[2][2] = 9 + 5 = 14.

Last row: [13, 13, 14]. Minimum is 13. Matches expected output.

Optimized Solution — Space-Optimized Python and JavaScript#

Python — In-Place#

from typing import List
 
class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        for i in range(1, n):
            for j in range(n):
                best = matrix[i - 1][j]
                if j > 0:
                    best = min(best, matrix[i - 1][j - 1])
                if j < n - 1:
                    best = min(best, matrix[i - 1][j + 1])
                matrix[i][j] += best
        return min(matrix[-1])

JavaScript — In-Place#

var minFallingPathSum = function (matrix) {
  const n = matrix.length;
  for (let i = 1; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
      let 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;
    }
  }
  return Math.min(...matrix[n - 1]);
};

If mutating the input is forbidden, allocate two rolling rows of length n and toggle between them — same time, O(n) extra space.

Complexity Analysis#

• Time: O(n^2). Each cell does O(1) work and we touch every cell.
• Space: O(1) extra with in-place mutation, O(n) with rolling rows, O(n^2) with full tabulation.
• Memoization: O(n^2) time but O(n^2) memory plus recursion stack — strictly worse than tabulation here.

Common Mistakes#

• Forgetting boundary checks. At j = 0, the diagonal-left predecessor is out of range; at j = n - 1, the diagonal-right is. Skipping these checks reads from invalid indices.
• Mutating input without permission. Always ask before touching the caller's matrix; some interviewers flag it as a side effect bug.
• Confusing this with Triangle (LeetCode 120). Triangle has variable row widths; Minimum Falling Path Sum is square. The recurrences are different at the boundaries.
• Using max instead of min. Read the prompt carefully; the variant with maximum exists too.
• Initializing the DP table with zeros. That mistakes the first row for free; copy the first row of matrix instead.

Interview Tips#

• Lead with the recurrence: "Each cell has up to three predecessors, and we pick the minimum among them." That is the cleanest opening.
• Discuss the in-place vs. out-of-place tradeoff. Production code usually avoids mutating inputs; interview code can opt in for O(1) memory.
• Demonstrate the boundary handling carefully — most bugs live there.
• Mention the bottom-up direction as a follow-up; it does not change correctness but tests flexibility.

Follow-up Questions#

• Allow only "non-zero shifts" — adjacent rows must come from different columns (LeetCode 1289 Minimum Falling Path Sum II). State expands or you keep the two smallest values per row.
• Reconstruct the optimal path. Store predecessor pointers in a parallel table.
• Maximize the falling path sum instead. Same shape, swap min for max.
• Generalize to non-square grids of size m x n. The DP and complexity are identical.

Key Takeaways#

• Minimum Falling Path Sum is the friendliest grid-DP recurrence: each cell has up to three predecessors, take the minimum, add the current value.
• Tabulation runs in O(n^2) time; space drops from O(n^2) to O(n) with rolling rows or O(1) with in-place mutation.
• Boundary handling at j = 0 and j = n - 1 is the single most common bug — guard the diagonal moves.
• The DP demonstrates optimal substructure cleanly: the best path ending at a cell uses one of three best paths ending at predecessors.
• Bottom-up direction (last row to first) is an equivalent formulation; mentioning it shows DP-direction flexibility.
• Mastering this template prepares you for Triangle, Cherry Pickup, and Minimum Falling Path Sum II at FAANG interviews.