Minimum Falling Path Sum II
HardPrompt
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] <= 99
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a 2D dynamic programming table to solve the problem. Let dp[i][j] represent the minimum sum of a falling path ending at the cell (i, j). We build this table row by row, from top to bottom.
Algorithm
- Get the dimension
nof thegrid. Ifnis 1, returngrid[0][0]. - Create a 2D DP array
dpof sizen x n. - Initialize the first row of
dpwith the values from the first row ofgrid:dp[0][j] = grid[0][j]forjfrom0ton-1. - Iterate through the rows from
i = 1ton-1. - For each row
i, iterate through the columnsj = 0ton-1. - Inside this loop, find the minimum value in the previous row
dp[i-1]excludingdp[i-1][j].- Initialize
minPrevRow = Integer.MAX_VALUE. - Iterate
kfrom0ton-1. - If
k != j, updateminPrevRow = min(minPrevRow, dp[i-1][k]).
- Initialize
- Calculate
dp[i][j] = grid[i][j] + minPrevRow. - After filling the
dptable, find the minimum value in the last rowdp[n-1]. - Return this minimum value.
Walkthrough
The core idea is to define a recurrence relation. The minimum path sum to reach grid[i][j] is grid[i][j] plus the minimum path sum of the previous row i-1, with the constraint that we cannot come from the same column j.
So, dp[i][j] = grid[i][j] + min(dp[i-1][k]) for all k where k != j.
We initialize a dp table of the same size as the grid. The first row of dp is the same as the first row of grid, as there's no path before it.
Then, we iterate from the second row to the last. For each cell (i, j), we calculate dp[i][j] by finding the minimum value in the previous row dp[i-1] excluding the element at column j, and adding it to grid[i][j].
After filling the entire dp table, the minimum value in the last row dp[n-1] will be the overall minimum falling path sum.
class Solution { public int minFallingPathSum(int[][] grid) { int n = grid.length; if (n == 1) { return grid[0][0]; } int[][] dp = new int[n][n]; // Initialize the first row of dp table for (int j = 0; j < n; j++) { dp[0][j] = grid[0][j]; } // Fill the rest of the dp table for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { int minPrevRow = Integer.MAX_VALUE; for (int k = 0; k < n; k++) { if (k != j) { minPrevRow = Math.min(minPrevRow, dp[i - 1][k]); } } dp[i][j] = grid[i][j] + minPrevRow; } } // Find the minimum sum in the last row int minSum = Integer.MAX_VALUE; for (int j = 0; j < n; j++) { minSum = Math.min(minSum, dp[n - 1][j]); } return minSum; }}Complexity
Time
O(n^3). We have three nested loops. The outer two iterate through each cell of the grid (`n*n`), and for each cell, the inner loop iterates through the `n` columns of the previous row.
Space
O(n^2). We use an additional `dp` table of size `n x n`.
Trade-offs
Pros
Conceptually straightforward and easy to understand.
Correctly solves the problem by exploring all valid paths systematically.
Cons
Inefficient due to the nested loop structure.
High time complexity makes it slow for larger grids, potentially leading to a 'Time Limit Exceeded' error on online judges.
This approach improves upon the standard DP by optimizing the calculation for each state. Instead of re-calculating the minimum of the previous row for each cell, we can pre-calculate the two smallest values of the previous row. This reduces the time complexity significantly.
Algorithm
- Get the dimension
nof thegrid. Ifnis 1, returngrid[0][0]. - Create a 2D DP array
dpof sizen x n. - Initialize the first row of
dpwith the values from the first row ofgrid. - Iterate through the rows from
i = 1ton-1. - In each iteration
i, find the two smallest values (min1,min2) and the index of the smallest value (min1_idx) in the previous rowdp[i-1].- Initialize
min1 = Integer.MAX_VALUE,min2 = Integer.MAX_VALUE,min1_idx = -1. - Iterate
kfrom0ton-1overdp[i-1]. - If
dp[i-1][k]is smaller thanmin1, updatemin2 = min1,min1 = dp[i-1][k], andmin1_idx = k. - Else if
dp[i-1][k]is smaller thanmin2, updatemin2 = dp[i-1][k].
- Initialize
- For each column
jin the current rowi:- If
j == min1_idx,dp[i][j] = grid[i][j] + min2. - Otherwise,
dp[i][j] = grid[i][j] + min1.
- If
- After filling the
dptable, find the minimum value in the last rowdp[n-1]. - Return this minimum value.
Walkthrough
The key observation is that for any cell (i, j), the minimum path sum from the previous row i-1 will either be the absolute minimum of that row (min1) or the second minimum (min2).
- If the current column
jis different from the column of the previous row's minimum (min1_idx), we can usemin1. - If the current column
jis the same asmin1_idx, we are forced to take the second best option from the previous row, which ismin2.
So, for each row i, we first find the two smallest values (min1, min2) and the index of min1 from the previous row dp[i-1]. This can be done in a single pass O(n). Then, we iterate through the columns j of the current row i and calculate dp[i][j] in O(1) time using min1 and min2.
class Solution { public int minFallingPathSum(int[][] grid) { int n = grid.length; if (n == 1) { return grid[0][0]; } int[][] dp = new int[n][n]; System.arraycopy(grid[0], 0, dp[0], 0, n); for (int i = 1; i < n; i++) { // Find the two smallest values in the previous row (dp[i-1]) int min1 = Integer.MAX_VALUE; int min2 = Integer.MAX_VALUE; int min1_idx = -1; for (int j = 0; j < n; j++) { if (dp[i - 1][j] < min1) { min2 = min1; min1 = dp[i - 1][j]; min1_idx = j; } else if (dp[i - 1][j] < min2) { min2 = dp[i - 1][j]; } } // Fill the current row of dp table for (int j = 0; j < n; j++) { if (j == min1_idx) { dp[i][j] = grid[i][j] + min2; } else { dp[i][j] = grid[i][j] + min1; } } } int result = Integer.MAX_VALUE; for (int j = 0; j < n; j++) { result = Math.min(result, dp[n - 1][j]); } return result; }}Complexity
Time
O(n^2). The outer loop runs `n` times. Inside, we have two separate loops that each run `n` times (one to find min1/min2, one to fill the current DP row). So, `O(n * (n + n)) = O(n^2)`.
Space
O(n^2). We use an additional `dp` table of size `n x n`.
Trade-offs
Pros
Much more efficient than the standard DP approach.
Reduces the time complexity from cubic to quadratic.
Cons
Still requires significant extra space for the DP table.
This is the most efficient approach. It builds upon the optimized DP logic but reduces the space complexity. Since the calculation for the current row only depends on the values from the immediately preceding row, we don't need to store the entire DP table. We can modify the input grid in-place to achieve constant extra space.
Algorithm
- Get the dimension
nof thegrid. Ifnis 1, returngrid[0][0]. - Iterate through the rows of the
gridfromi = 1ton-1. - In each iteration
i, find the two smallest values (min1,min2) and the index of the smallest value (min1_idx) in the previous rowgrid[i-1]. - For each column
jin the current rowi:- If
j == min1_idx, updategrid[i][j] = grid[i][j] + min2. - Otherwise, update
grid[i][j] = grid[i][j] + min1.
- If
- After the loops complete, the last row of the
gridcontains the total sums for all falling paths ending at each column. - Find the minimum value in the last row
grid[n-1]and return it.
Walkthrough
The logic is identical to the optimized O(n^2) DP approach. The only difference is in the implementation of space usage. Instead of a full dp table, we can modify the input grid itself to store the DP values. grid[i][j] will be updated to store the minimum falling path sum ending at that cell. This is possible because once we compute row i, the original values of grid[i-1] are no longer needed for subsequent calculations.
We iterate from the second row. For each row, we find the two minimums from the updated previous row. Then we update the current row's values by adding the appropriate minimum.
class Solution { public int minFallingPathSum(int[][] grid) { int n = grid.length; if (n == 1) { return grid[0][0]; } for (int i = 1; i < n; i++) { // Find the two smallest values in the previous row int min1 = Integer.MAX_VALUE; int min2 = Integer.MAX_VALUE; int min1_idx = -1; for (int j = 0; j < n; j++) { if (grid[i - 1][j] < min1) { min2 = min1; min1 = grid[i - 1][j]; min1_idx = j; } else if (grid[i - 1][j] < min2) { min2 = grid[i - 1][j]; } } // Update the current row with the new path sums for (int j = 0; j < n; j++) { if (j == min1_idx) { grid[i][j] += min2; } else { grid[i][j] += min1; } } } // Find the minimum in the last row int result = Integer.MAX_VALUE; for (int j = 0; j < n; j++) { result = Math.min(result, grid[n - 1][j]); } return result; }}Complexity
Time
O(n^2). The complexity remains the same as the previous optimized approach. We iterate through the grid once.
Space
O(1). We modify the grid in-place and only use a few variables to store the minimums, resulting in constant extra space. If an auxiliary array is used instead of modifying the input, the space complexity would be `O(n)`.
Trade-offs
Pros
Optimal time complexity for this problem.
Optimal space complexity, as it uses constant extra space (by modifying the input).
Cons
Modifies the input array, which might not be desirable in all contexts. If modification is disallowed, an
O(n)space solution using an auxiliary array for the previous row is a simple alternative.
Solutions
Solution
class Solution {public int minFallingPathSum(int[][] grid) { int n = grid.length; int[][] f = new int[n + 1][n]; final int inf = 1 << 30; for (int i = 1; i <= n; ++i) { for (int j = 0; j < n; ++j) { int x = inf; for (int k = 0; k < n; ++k) { if (k != j) { x = Math.min(x, f[i - 1][k]); } } f[i][j] = grid[i - 1][j] + (x == inf ? 0 : x); } } int ans = inf; for (int x : f[n]) { ans = Math.min(ans, x); } return ans; }}class Solution {public: int minFallingPathSum(vector<vector<int>> &grid) { int n = grid.size(); int f[n + 1][n]; memset(f, 0, sizeof(f)); const int inf = 1 << 30; for (int i = 1; i <= n; ++i) { for (int j = 0; j < n; ++j) { int x = inf; for (int k = 0; k < n; ++k) { if (k != j) { x = min(x, f[i - 1][k]); } } f[i][j] = grid[i - 1][j] + (x == inf ? 0 : x); } } return *min_element(f[n], f[n] + n); }};class Solution: def minFallingPathSum(self, grid: List[List[int]]) -> int: n = len(grid) f = [[0] * n for _ in range(n + 1)] for i, row in enumerate(grid, 1): for j, v in enumerate(row): x = min((f[i - 1][k] for k in range(n) if k != j), default=0) f[i][j] = v + x return min(f[n])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.