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.
This approach uses dynamic programming to keep track of the minimum sum at each position and makes sure no two consecutive rows select a value from the same column. We use a 2D DP array where dp[i][j] represents the minimum path sum to reach element grid[i][j]. Expand on each row by calculating potential path sums from the previous row using existing minimum path sums stored in the DP table.
This C solution uses an integer array dp to store the minimum path sums, ensuring no same column values from contiguous rows are included by looping to check all columns except the current column.
Time Complexity: O(n^3) where n is the number of rows or columns in the grid.
Space Complexity: O(n^2) for the auxiliary DP array.
This approach enhances space efficiency by using two 1D arrays to store only the last row and the current row values of the DP computations. At each step, we compute the minimum path and store it, minimizing space usage to O(n) instead of O(n^2).
The C solution employs two arrays, prev and curr, to alternate between rows of calculations, minimizing memory use while maintaining previous state information for each row during traversal.
Time Complexity: O(n^3) because Min operation checks all columns for each column in each row.
Space Complexity: O(n) using two 1D arrays for storing current and previous row states in DP.
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Tracking | Time Complexity: O(n^3) where n is the number of rows or columns in the grid. |
| Dynamic Programming with Space Optimization | Time Complexity: O(n^3) because Min operation checks all columns for each column in each row. |
| 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 |
Minimum Falling Path Sum II - Leetcode 1289 - Python • NeetCodeIO • 10,644 views views
Watch 9 more video solutions →Practice Minimum Falling Path Sum II with our built-in code editor and test cases.
Practice on FleetCode