Minimum Falling Path Sum II

This problem asks for the minimum sum of a falling path in a square grid where no two adjacent elements in the path are in the same column. We can solve this using dynamic programming.

Approach 1: Dynamic Programming with 2D array

This approach uses a 2D array f to store the minimum falling path sum up to each cell. f[i][j] represents the minimum sum ending at cell (i, j).

Algorithm:

1. Initialization: Create a 2D array f of size (n+1) x n, where n is the size of the grid. Initialize the first row of f to 0.

2. Iteration: Iterate through the grid row by row. For each cell (i, j):

   • Find the minimum falling path sum among all cells in the previous row (i-1) excluding the column j. This is done by iterating through the previous row and taking the minimum value, excluding the cell in the same column.
   • Update f[i][j] to be the current cell's value plus the minimum sum found in step 2.

3. Result: After iterating through all cells, the minimum falling path sum will be the minimum value in the last row of f.

Time Complexity: O(n^2), where n is the size of the grid. The nested loops iterate through each cell once.

Space Complexity: O(n^2) due to the 2D array f.

Approach 2: Optimized Dynamic Programming

This approach improves space complexity by using only a few variables to track the minimum and second minimum values from the previous row. This avoids the need for a large 2D array.

Algorithm:

1. Initialization: Initialize f and g (minimum and second minimum sums from the previous row), and fp (column index of f) to 0 and -1 respectively.

2. Iteration: Iterate through the grid row by row. For each row:

   • Initialize ff and gg (minimum and second minimum sums for the current row), and ffp (column index of ff) to infinity and -1 respectively.
   • Iterate through each cell in the row. Calculate the sum s by adding the current cell's value to either f or g (depending on whether the current column is the same as fp).
   • Update ff, gg, and ffp to maintain the minimum and second minimum sums for the current row.

3. Result: After iterating through all rows, f will contain the minimum falling path sum.

Time Complexity: O(n^2), same as Approach 1.

Space Complexity: O(1). This approach only uses a constant number of variables, regardless of the input size.

Code Examples (Python and Java)

Approach 1 (Python):

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])
 

Approach 2 (Java):

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int f = 0, g = 0;
        int fp = -1;
        final int inf = 1 << 30; // Representing infinity
        for (int[] row : grid) {
            int ff = inf, gg = inf;
            int ffp = -1;
            for (int j = 0; j < row.length; ++j) {
                int s = (j != fp ? f : g) + row[j];
                if (s < ff) {
                    gg = ff;
                    ff = s;
                    ffp = j;
                } else if (s < gg) {
                    gg = s;
                }
            }
            f = ff;
            g = gg;
            fp = ffp;
        }
        return f;
    }
}

The other languages (C++, Go) would have similar implementations, following the same algorithmic approach. Approach 2 is generally preferred due to its better space complexity.