Code Implementation

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = grid[0][:]
        for i in range(1, n):
            min1 = min2 = float('inf')
            idx1 = idx2 = -1
            for j in range(n):
                if dp[j] < min1:
                    min2, idx2 = min1, idx1
                    min1, idx1 = dp[j], j
                elif dp[j] < min2:
                    min2, idx2 = dp[j], j
            new_dp = [0] * n
            for j in range(n):
                if j != idx1:
                    new_dp[j] = grid[i][j] + min1
                else:
                    new_dp[j] = grid[i][j] + min2
            dp = new_dp
        return min(dp)
      

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> dp = grid[0];
        for (int i = 1; i < n; ++i) {
            int min1 = INT_MAX, min2 = INT_MAX, idx1 = -1, idx2 = -1;
            for (int j = 0; j < n; ++j) {
                if (dp[j] < min1) {
                    min2 = min1; idx2 = idx1;
                    min1 = dp[j]; idx1 = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j]; idx2 = j;
                }
            }
            vector<int> new_dp(n);
            for (int j = 0; j < n; ++j) {
                new_dp[j] = grid[i][j] + (j != idx1 ? min1 : min2);
            }
            dp = new_dp;
        }
        return *min_element(dp.begin(), dp.end());
    }
};
      

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[] dp = grid[0].clone();
        for (int i = 1; i < n; ++i) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            int idx1 = -1, idx2 = -1;
            for (int j = 0; j < n; ++j) {
                if (dp[j] < min1) {
                    min2 = min1; idx2 = idx1;
                    min1 = dp[j]; idx1 = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j]; idx2 = j;
                }
            }
            int[] new_dp = new int[n];
            for (int j = 0; j < n; ++j) {
                new_dp[j] = grid[i][j] + (j != idx1 ? min1 : min2);
            }
            dp = new_dp;
        }
        int res = Integer.MAX_VALUE;
        for (int x : dp) res = Math.min(res, x);
        return res;
    }
}
      

var minFallingPathSum = function(grid) {
    const n = grid.length;
    let dp = grid[0].slice();
    for (let i = 1; i < n; ++i) {
        let min1 = Infinity, min2 = Infinity, idx1 = -1, idx2 = -1;
        for (let j = 0; j < n; ++j) {
            if (dp[j] < min1) {
                min2 = min1; idx2 = idx1;
                min1 = dp[j]; idx1 = j;
            } else if (dp[j] < min2) {
                min2 = dp[j]; idx2 = j;
            }
        }
        let new_dp = new Array(n);
        for (let j = 0; j < n; ++j) {
            new_dp[j] = grid[i][j] + (j !== idx1 ? min1 : min2);
        }
        dp = new_dp;
    }
    return Math.min(...dp);
};
      

Problem Description

You are given an n x n integer matrix grid. A falling path starts at any element in the first row and chooses one element from each row, moving down one row at a time. For each move, you must pick a different column than the previous row (you cannot reuse the same column as the previous step).

Your goal is to find the minimum sum of a falling path from the first row to the last row, following these rules:

• Each path picks exactly one element from each row.
• No two consecutive elements are from the same column.

Thought Process

At first glance, the problem looks similar to finding the minimum path sum in a grid, but with an extra twist: you cannot pick the same column in consecutive rows. This restriction means that for each step, your choice depends on your previous column.

A brute-force approach would be to try all possible paths, but since the number of paths grows exponentially with the size of the matrix, this is not practical for large inputs.

The next idea is to use dynamic programming to keep track of the minimum sum to reach each cell, while making sure not to reuse columns. However, a naive DP would require checking all other columns every time, leading to an O(n³) solution. Is there a way to optimize this?

If for each row, we know the two smallest sums from the previous row (and their column indices), then for each cell, we can select the minimum sum from the previous row that does not use the same column. This reduces the time complexity dramatically.

Solution Approach

Let's break down the optimized dynamic programming solution step by step:

1. Initialization:
   • Start with the first row. The minimum sum to reach each cell in the first row is just the value of that cell.
   • Store this row as your current DP state.
2. Iterate through each subsequent row:
   • For each row, find the two smallest values in the previous DP row, along with their column indices.
   • For each cell in the current row:
     • If its column is not the same as the minimum column from above, use the smallest value.
     • If its column is the minimum column, use the second smallest value (to avoid reusing the same column).
   • Update the DP array for this row accordingly.
3. Final Answer:
   • After processing all rows, the answer is the minimum value in the last DP row.

This approach works because at each step, we only need to know the two smallest sums from the previous row, and for each cell, we can efficiently decide which to use based on the column index.

Example Walkthrough

Let's walk through an example using the following grid:

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

Step 1 (Initialization):
The first row is [2, 1, 3]. This is our initial DP state.

Step 2 (Row 2):
Previous DP: [2, 1, 3]
- Min1 = 1 (col 1), Min2 = 2 (col 0)

• Cell (1,0): 6 + (min1 from col 1 ≠ 0) → 6 + 1 = 7
• Cell (1,1): 5 + (min2 from col 0 ≠ 1) → 5 + 2 = 7
• Cell (1,2): 4 + (min1 from col 1 ≠ 2) → 4 + 1 = 5

Step 3 (Row 3):
Previous DP: [7, 7, 5]
- Min1 = 5 (col 2), Min2 = 7 (col 0 or 1)

• Cell (2,0): 7 + (min1 from col 2 ≠ 0) → 7 + 5 = 12
• Cell (2,1): 8 + (min1 from col 2 ≠ 1) → 8 + 5 = 13
• Cell (2,2): 9 + (min2 from col 0 or 1 ≠ 2) → 9 + 7 = 16

Final Answer: The minimum value in the last row is 12.

Time and Space Complexity

Brute-force Approach:

• There are n choices for each row, and n rows, leading to O(nⁿ) paths — not feasible for large n.

• For each of n rows, we process n columns.
• For each row, we find the two smallest values in O(n), and update each cell in O(1).
• Total time complexity: O(n²).
• Space complexity: O(n) for the DP array (since we only need the previous row at any time).

This is a significant improvement over the brute-force approach and works efficiently for reasonably large matrices.

Summary

The Minimum Falling Path Sum II problem is a classic example of using dynamic programming with an additional constraint (no consecutive columns). By keeping track of the two smallest values in each DP row, we avoid unnecessary computations and reduce the time complexity to O(n²). This approach is both efficient and elegant, relying on careful observation of the problem's structure. It's a great demonstration of how optimizing DP transitions can lead to substantial performance gains.