1289. Minimum Falling Path Sum II

Problem Description

Given an n x n integer matrix named grid, the objective is to calculate the minimum sum of what is termed a "falling path with non-zero shifts." A falling path with non-zero shifts is a selection of one element from each row of the matrix such that for any two elements chosen from consecutive rows, they are not situated in the same column. Essentially, we need to find a path from the top to the bottom of the matrix, selecting one element from each row, without reusing columns in consecutive rows, and adding those elements to achieve the smallest possible sum.

Intuition

To find the minimum falling path sum, we can use a dynamic programming approach that builds upon the answer from the previous row to compute the answer for the current row. Specifically, for each row, we keep track of the smallest value (f) and the second smallest (g) from the previous row. This is because we cannot pick elements from the same column in consecutive rows, so we need to have a backup option in case the smallest value from the previous row is in the same column.

The solution progressively calculates the sum of each row, taking into account the smallest sums of the previous row while avoiding the same column positions. For each row, we iterate through its columns and try to find the smallest sum (ff) by either choosing the smallest sum for different columns or the second smallest sum (gg) when the same column as the previous smallest is encountered. This way, we prevent two consecutive rows from having elements in the same column. By keeping an updated minimum (f) and second minimum (g) and their column positions (fp), we can continue to build up the solution row by row, until we reach the bottom of the matrix. The minimum sum of the last calculated row will be the final answer, which provides the minimum sum of a falling path with non-zero shifts as required.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution approach makes use of dynamic programming as its core strategy. The idea is to iterate over each row and compute the minimum and the second minimum values required to reach each position without considering the previous row's column. By doing so, we ensure compliance with the problem's condition that no two elements in adjacent rows are in the same column.

A crucial aspect of the solution is tracking the minimum (f) and the second minimum (g) costs to reach the current row while recording the column index (fp) of the minimum cost from the previous row. This information is used to decide whether to use the minimum or second minimum cost when calculating the current row’s values.

Here's a walkthrough of the algorithm using the problem's terminology:

1. Initialize f and g to 0 as the initial minimum and second minimum costs, respectively. Initialize fp to -1 to indicate no previous column.

2. For each row row in the matrix grid:

   • Initialize ff and gg to inf as placeholders for the current row's minimum and second minimum costs.
   • Initialize ffp to -1, which will hold the column index of the current row's minimum cost.
   • For each value v in row, with its index j:
     • Calculate the sum s by adding v to g if the current column j is the same as fp (to avoid picking two elements from the same column in adjacent rows), or to f otherwise.
     • If the calculated sum s is less than ff:
       • Assign the value of ff to gg, as ff will now hold the new minimum, s.
       • Update ff with the new minimum, s.
       • Update ffp with the current column index j, indicating the column of the new minimum.
     • Else if s is less than gg, update gg with the new second minimum, s.

3. After the loop, assign ff to f, gg to g, and ffp to fp for the next iteration. This step effectively moves the minimum and second minimum costs, along with the column index of the minimum, to the next row.

4. Once all rows have been processed, f holds the minimum sum of a falling path with non-zero shifts and is returned as the result.

Throughout this process, the algorithm avoids using the same column for consecutive rows by considering g (the second smallest) whenever the current column is the same as the previous row's minimum. By keeping a running tally of the smallest sums that conform to the problem's rules, the algorithm ensures optimal substructure—one of the hallmarks of dynamic programming. In the end, the minimum sum of the final row provides the answer.

This solution has a time complexity of O(n^2) where n is the number of rows (or columns) in the matrix, making it efficient enough to handle larger matrices.

The code is a practical implementation of this approach and manifests the described dynamic programming strategy effectively.

Example Walkthrough

Let's use a 3x3 matrix as a small example to illustrate the solution approach.

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

Following the dynamic programming approach to find the minimum falling path sum with non-zero shifts:

1. Initialize f and g to 0, and fp to -1 (no previous column):

1f = 0, g = 0, fp = -1

2. For the first row, since there are no previous rows, the minimum (f) and second minimum (g) sums are the smallest and second smallest values from the row itself. We then determine f, g, and fp:

1Row 0: [2, 1, 3]
2f = 1, g = 2, fp = 1 (index of minimum value in row 0)

3. Move to the second row, update ff, gg, and ffp as we find the sums for this row:

1Row 1: [6, 5, 4], Previous `fp` = 1
2
3For column 0: s = grid[1][0] + g = 6 + 2 = 8 (since column 0 is not `fp`)
4For column 1: Cannot choose since `fp` is 1 (same column as the previous minimum)
5For column 2: s = grid[1][2] + f = 4 + 1 = 5 (since column 2 is not `fp`)
6
7Update `f`, `g`, and `fp` for this row:
8ff = 5, gg = 8, ffp = 2

4. After iterating through the second row, update f, g, and fp with the new values:

1f = ff = 5, g = gg = 8, fp = ffp = 2

5. Repeat the process for the third row:

1Row 2: [7, 8, 9], Previous `fp` = 2
2
3For column 0: s = grid[2][0] + g = 7 + 8 = 15 (since column 0 is not `fp`)
4For column 1: s = grid[2][1] + f = 8 + 5 = 13 (since column 1 is not `fp`)
5For column 2: Cannot choose since `fp` is 2 (same column as the previous minimum)
6
7Only two valid sums for this row:
8ff = 13, gg = 15, ffp = 1

6. After the final row, we update f, g, and fp for the last time:

1f = ff = 13, g = gg = 15, fp = ffp = 1

The minimum sum of a falling path with non-zero shifts is held in f, which is 13 in this case.

This completes the example for the 3x3 matrix, the path that leads to the minimum sum would be from the elements grid[0][1], grid[1][2], and grid[2][1], resulting in the path 1 -> 4 -> 8, with a sum of 13.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n * m), where n is the number of rows and m is the number of columns in the input grid. This is because the code iterates through each row with an outer loop and each column with an inner loop, computing the minimum falling path sum in a single pass.

Space Complexity

The space complexity of the code is O(1). Although the algorithm iterates through the entire grid, it uses only a constant amount of additional space for the variables f, g, fp, ff, gg, and ffp, regardless of the size of the input grid.

Learn more about how to find time and space complexity quickly using problem constraints.