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] <= 99Minimum Falling Path Sum II extends the classic falling path problem by adding a constraint: you cannot choose the same column in consecutive rows. A straightforward dynamic programming solution computes the minimum cost for each cell by checking all values from the previous row except the same column. While intuitive, this approach results in O(n^3) time for an n x n matrix.
A more optimized strategy observes that each row only needs the smallest and second smallest values from the previous row. If the current column matches the index of the smallest value, use the second smallest instead; otherwise use the smallest. This eliminates the need to scan all columns for every cell.
By tracking these two minimum values per row, the algorithm reduces the complexity to O(n^2) time with minimal additional space. This optimization is the key idea interviewers typically expect for this hard dynamic programming problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Basic Dynamic Programming (check all columns) | O(n^3) | O(n^2) |
| Optimized DP using smallest & second smallest values | O(n^2) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming.
Let dp[i][j] be the answer for the first i rows such that column j is chosen from row i.
Use the concept of cumulative array to optimize the complexity of the solution.
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.
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.
1#include <vector>
2#include <algorithm>
3int minFallingPathSum(std::vector<std::vector<int>>& grid) {
4 int n = grid.size();
5 std::vector<std::vector<int>> dp = grid;
6 for (int i = 1; i < n; i++) {
7 for (int j = 0; j < n; j++) {
8 int minPrev = INT_MAX;
9 for (int k = 0; k < n; k++) {
10 if (k != j) minPrev = std::min(minPrev, dp[i - 1][k]);
11 }
12 dp[i][j] = grid[i][j] + minPrev;
13 }
}
return *std::min_element(dp[n - 1].begin(), dp[n - 1].end());
}This C++ solution initializes a DP vector identical to the grid and updates it with the minimum possible sums ending at each element. It avoids choosing the same column.
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).
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.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of matrix dynamic programming problems like this are common in FAANG-style interviews. Interviewers often expect candidates to move from a naive DP solution to the optimized approach that tracks minimum values efficiently.
The optimal approach uses dynamic programming while tracking the smallest and second smallest values from the previous row. This allows you to avoid selecting the same column without scanning the entire row each time. It reduces the time complexity from O(n^3) to O(n^2).
Arrays or matrices are used to store dynamic programming states for each row. The algorithm may also maintain a few variables to track the smallest and second smallest values in the previous row. No advanced data structures are required.
Tracking the two minimum values helps handle the restriction that consecutive elements cannot come from the same column. If the current column matches the index of the smallest value from the previous row, the algorithm uses the second smallest instead. This keeps the computation efficient.
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.