Minimum Falling Path Sum II

How it works

We can further optimize by not storing an entire array of pairs. Instead, we only track four values: the index and value of the smallest element, and the index and value of the second smallest element from the previous row. For each cell in the current row, we add the appropriate previous minimum based on column matching. Then we update our tracked values for the next iteration. This achieves O(n^2) time with O(1) extra space.

Steps

1. Initialize dpIdx1, dpIdx2 (indices of first and second smallest) and dpVal1, dpVal2 (their values) to represent the previous row's state.
2. For each row:
   • Track new smallest and second smallest values and indices.
   • For each column j:
     • If j != dpIdx1, add dpVal1; otherwise add dpVal2.
     • Update the running smallest and second smallest for this row.
3. After processing all rows, return dpVal1 (the overall minimum).

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(1) extra space.

Things to watch for

Confusing with Standard Falling Path Sum

Unlike the standard falling path problem where you move to adjacent columns, this variant requires choosing a different column in each row. Using the adjacent-column logic from the standard problem will produce incorrect results.

O(n^3) Time Complexity Trap

A naive approach checks all n columns from the previous row for each of n^2 cells, resulting in O(n^3) time. The key optimization is tracking only the two smallest values from each row, since you only need the second smallest when the current column matches the smallest.

Edge Case with Single Column Grid

When n = 1, there is only one column, making it impossible to pick a different column in each row after the first. The answer is simply grid[0][0] since a 1x1 grid has only one cell. Failing to handle this edge case causes index errors or infinite loops.

Incorrect Second Minimum Tracking

When optimizing to O(n^2), you must correctly track both the minimum and second minimum values along with their column indices. Common mistakes include not updating both values properly, using the wrong index for comparison, or forgetting to handle ties when multiple columns have the same minimum value.

Integer Overflow with Large Negative Values

Grid values can be negative, so initializing with INT_MIN as a sentinel can cause overflow when added to grid values. Use a distinct sentinel value or nullable type to distinguish uncomputed states from valid negative sums.

from typing import List

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1:
            return grid[0][0]

        dp_idx1 = dp_idx2 = -1
        dp_val1 = dp_val2 = 0

        for i in range(n):
            nextDp_idx1 = nextDp_idx2 = -1
            nextDp_val1 = nextDp_val2 = float("inf")

            for j in range(n):
                cur = dp_val1 if j != dp_idx1 else dp_val2
                cur += grid[i][j]

                if nextDp_idx1 == -1 or cur < nextDp_val1:
                    nextDp_idx2, nextDp_val2 = nextDp_idx1, nextDp_val1
                    nextDp_idx1, nextDp_val1 = j, cur
                elif nextDp_idx2 == -1 or cur < nextDp_val2:
                    nextDp_idx2, nextDp_val2 = j, cur

            dp_idx1, dp_idx2, dp_val1, dp_val2 = nextDp_idx1, nextDp_idx2, nextDp_val1, nextDp_val2

        return dp_val1

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 1) {
            return grid[0][0];
        }

        int dpIdx1 = -1, dpIdx2 = -1;
        int dpVal1 = 0, dpVal2 = 0;

        for (int i = 1; i < n; i++) {
            int nextDpIdx1 = -1, nextDpIdx2 = -1;
            int nextDpVal1 = INT_MAX, nextDpVal2 = INT_MAX;

            for (int j = 0; j < n; j++) {
                int cur = (j != dpIdx1) ? dpVal1 : dpVal2;
                cur += grid[i][j];

                if (nextDpIdx1 == -1 || cur < nextDpVal1) {
                    nextDpIdx2 = nextDpIdx1;
                    nextDpVal2 = nextDpVal1;
                    nextDpIdx1 = j;
                    nextDpVal1 = cur;
                } else if (nextDpIdx2 == -1 || cur < nextDpVal2) {
                    nextDpIdx2 = j;
                    nextDpVal2 = cur;
                }
            }

            dpIdx1 = nextDpIdx1;
            dpIdx2 = nextDpIdx2;
            dpVal1 = nextDpVal1;
            dpVal2 = nextDpVal2;
        }

        return dpVal1;
    }
};