LeetCode 931: Minimum Falling Path Sum

Problem Restatement

We are given an n x n integer matrix.

A falling path starts at any cell in the first row. From a cell (row, col), the next cell must be in the next row and one of these columns:

col - 1
col
col + 1

So from (row, col), we may move to:

(row + 1, col - 1)
(row + 1, col)
(row + 1, col + 1)

as long as the column stays inside the matrix.

Return the minimum possible sum of a falling path from the first row to the last row. The official statement defines the same down-left, down, and down-right moves.

Input and Output

Function shape:

class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        ...

Examples

Example 1:

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

One minimum falling path is:

1 -> 5 -> 7

The sum is:

1 + 5 + 7 = 13

So the answer is:

13

Example 2:

matrix = [
    [-19, 57],
    [-40, -5],
]

The best path is:

-19 -> -40

The sum is:

-59

So the answer is:

-59

First Thought: Try Every Path

A direct approach is to start from every cell in the first row and recursively try every valid move.

From each cell, we may have up to three choices in the next row.

This creates many possible paths.

For a matrix with n rows, the number of paths can grow exponentially, so plain recursion is too slow.

The repeated work is clear: many different paths can reach the same cell. Once we know the minimum path sum ending at a cell, we should reuse it.

Key Insight

Use dynamic programming.

Let:

dp[col]

mean the minimum falling path sum ending at column col in the current row.

For the first row, the best path ending at each column is just the cell value itself.

For every later row, a cell (row, col) can be reached only from the previous row at:

col - 1
col
col + 1

So the transition is:

new_dp[col] = matrix[row][col] + min(
    dp[col - 1],
    dp[col],
    dp[col + 1]
)

We ignore invalid columns outside the matrix.

Algorithm

Initialize:

dp = matrix[0][:]

Then process each row starting from row 1.

For each column col:

1. Start with best_prev = dp[col].
2. If col > 0, compare with dp[col - 1].
3. If col + 1 < n, compare with dp[col + 1].
4. Set:

new_dp[col] = matrix[row][col] + best_prev

After processing the row, replace:

dp = new_dp

At the end, return:

min(dp)

because the path may end at any column in the last row.

Walkthrough

Use:

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

Initialize from the first row:

dp = [2, 1, 3]

Process row 1:

Now:

dp = [7, 6, 5]

Process row 2:

Now:

dp = [13, 13, 14]

Return:

13

Correctness

For the first row, dp[col] = matrix[0][col] is correct because a falling path may start at any cell in the first row, and the path sum is exactly that cell value.

Assume before processing row r, dp[col] stores the minimum falling path sum ending at cell (r - 1, col).

A falling path reaching (r, col) must come from one of the valid previous-row cells:

(r - 1, col - 1)
(r - 1, col)
(r - 1, col + 1)

By the assumption, dp already stores the best possible sum to each of those cells. Therefore, the best path ending at (r, col) is the current cell value plus the minimum of those valid previous sums.

The algorithm computes exactly this value for every column in row r, so after the row is processed, new_dp[col] is correct for that row.

By induction, after the last row, dp[col] stores the minimum falling path sum ending at each last-row column.

Since a valid path may end at any column in the last row, the minimum falling path sum overall is min(dp).

Complexity

Implementation

class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        dp = matrix[0][:]

        for row in range(1, n):
            new_dp = [0] * n

            for col in range(n):
                best_prev = dp[col]

                if col > 0:
                    best_prev = min(best_prev, dp[col - 1])

                if col + 1 < n:
                    best_prev = min(best_prev, dp[col + 1])

                new_dp[col] = matrix[row][col] + best_prev

            dp = new_dp

        return min(dp)

Code Explanation

We copy the first row:

dp = matrix[0][:]

This avoids modifying the input matrix.

Then we process each later row:

for row in range(1, n):

For each cell, the direct above cell is always valid:

best_prev = dp[col]

The upper-left cell is valid only when col > 0:

if col > 0:
    best_prev = min(best_prev, dp[col - 1])

The upper-right cell is valid only when col + 1 < n:

if col + 1 < n:
    best_prev = min(best_prev, dp[col + 1])

Then we add the current matrix value:

new_dp[col] = matrix[row][col] + best_prev

After the row is complete, the new row becomes the previous row for the next iteration:

dp = new_dp

The answer is the smallest path sum ending in the last row:

return min(dp)

Testing

def run_tests():
    s = Solution()

    assert s.minFallingPathSum([
        [2, 1, 3],
        [6, 5, 4],
        [7, 8, 9],
    ]) == 13

    assert s.minFallingPathSum([
        [-19, 57],
        [-40, -5],
    ]) == -59

    assert s.minFallingPathSum([
        [5],
    ]) == 5

    assert s.minFallingPathSum([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]) == 12

    assert s.minFallingPathSum([
        [100, -42, 30],
        [10, -5, 20],
        [7, 8, -9],
    ]) == -56

    print("all tests passed")

run_tests()