Watch 10 video solutions for Minimum Falling Path Sum II, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by NeetCodeIO has 10,644 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.
A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: 13 Explanation: 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
Constraints:
n == grid.length == grid[i].length1 <= n <= 200-99 <= grid[i][j] <= 99Problem Overview: Given an n x n grid, choose one number from each row such that no two chosen numbers from consecutive rows come from the same column. The goal is to minimize the total sum. This is a classic constrained transition problem in dynamic programming over a matrix.
Approach 1: Dynamic Programming with State Tracking (Time: O(n^2), Space: O(n^2))
Define dp[r][c] as the minimum sum of a falling path that ends at row r and column c. The transition requires picking the minimum value from the previous row except the same column. A naive scan for every column would cost O(n) per state, leading to O(n^3). Instead, track the smallest and second smallest values from the previous row along with their column indices. If the current column differs from the column of the smallest value, use that; otherwise use the second smallest.
This trick removes the inner scan and keeps transitions constant time. Iterate row by row, updating the DP table while maintaining the two minimum values for each row. The algorithm relies on efficient state reuse and works well for grid problems involving column restrictions, a common pattern in array and matrix DP.
Approach 2: Dynamic Programming with Space Optimization (Time: O(n^2), Space: O(n))
The full DP table is unnecessary because each row depends only on the previous one. Store just a single array representing the previous row's DP values. While processing the current row, compute the smallest and second smallest values from the previous array and update a new array for the current row.
After finishing a row, replace the previous array with the current one. This reduces memory usage from O(n^2) to O(n) while preserving the same transition logic and time complexity. The approach is particularly useful when n is large or when implementing the solution in memory-constrained environments.
Recommended for interviews: Interviewers expect the optimized dynamic programming solution using the smallest and second smallest values per row. Showing the straightforward DP idea first demonstrates understanding of the recurrence, but recognizing the min/second-min optimization proves strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with State Tracking | O(n^2) | O(n^2) | Clear DP formulation when learning the recurrence or debugging transitions |
| Dynamic Programming with Space Optimization | O(n^2) | O(n) | Preferred approach for interviews or large matrices where memory efficiency matters |