#1289

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Falling Path Sum II

Find the minimum sum of a falling path in a square matrix using dynamic programming while avoiding same-column selections.

array dynamic programming matrix

Problem Statement

Given an n x n integer matrix grid, determine the smallest sum obtainable by selecting one element from each row such that consecutive elements are never in the same column. Each choice must respect the non-zero shift constraint between rows, forming a falling path.

For example, with grid = [[1,2,3],[4,5,6],[7,8,9]], you must consider all paths where no two adjacent row selections are in the same column and return the minimum total sum. Constraints: n ranges from 1 to 200 and matrix values range from -99 to 99.

Examples

Example 1

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

Output: 13

The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2

Input: grid = [[7]]

Output: 7

Example details omitted.

Constraints

n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99

Solution Approach

Dynamic Programming with State Transitions

Create a DP matrix where dp[i][j] stores the minimum falling path sum ending at row i, column j. Update each dp[i][j] as the minimum of dp[i-1][k] + grid[i][j] for all k != j. This enforces the non-zero column shift.

Optimize Space Using Two Arrays

Instead of a full DP matrix, use two arrays: prevRow and currRow. Compute currRow[j] using prevRow values excluding the same column. Swap arrays after each row to reduce space to O(N).

Track Minimum Efficiently

To avoid redundant comparisons, track the smallest and second smallest values of the previous row. For each column, if it matches the smallest's column, use the second smallest; otherwise, use the smallest. This reduces time complexity to O(N^2) while respecting the non-zero shift.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(1)

Time complexity is O(N^2) because each cell requires scanning N previous elements, optimized by tracking smallest and second smallest values. Space can be reduced to O(N) by reusing row arrays instead of a full DP matrix.

What Interviewers Usually Probe

Are you enforcing the non-zero column shift in your state transitions?
Can you optimize your DP to reduce space while maintaining correctness?
How do you handle ties for minimum values when skipping the same column?

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude the same column in consecutive rows, leading to invalid paths.
Using full N x N DP without optimization, causing unnecessary space usage.
Incorrectly updating the minimum when multiple columns share the smallest value.

Follow-up variants

Allow negative and positive values, increasing the risk of selecting suboptimal paths.
Compute the maximum falling path sum instead of minimum, applying the same DP logic.
Handle non-square matrices where row and column counts differ, requiring adjusted state tracking.

FAQ

What is a falling path with non-zero shifts?

A falling path selects one element per row such that consecutive elements are never in the same column, enforcing a non-zero column shift.

How does state transition dynamic programming apply here?

Each cell's minimum path sum depends on the minimum values from the previous row excluding the same column, forming a classic DP state transition.

Can space be optimized in Minimum Falling Path Sum II?

Yes, by using two arrays for current and previous rows instead of a full DP matrix, space is reduced to O(N).

Why track the smallest and second smallest values?

Tracking these values allows fast selection of the minimum excluding the current column without scanning all previous columns.

What is the time complexity for this approach?

The optimized DP approach runs in O(N^2) time, processing each row and column while efficiently handling the column exclusion.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the minimum sum of the first $i$ rows, with the last number in the $j$-th column. The state transition equation is:

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        f = [0] * n
        for row in grid:
            g = row[:]
            for i in range(n):
                g[i] += min((f[j] for j in range(n) if j != i), default=0)
            f = g
        return min(f)

Continue Practicing

#1277 count square submatrices with all ones #1301 number of paths with max score #1349 maximum students taking exam