1289. Minimum Falling Path Sum II - Explanation

1. Recursion

Intuition

Unlike the standard falling path problem where we can move to adjacent columns, here we must pick a different column in each row. For each cell in a row, we recursively try all columns in the next row except the current one. This constraint increases complexity since we need to consider more transitions. The brute force approach explores all valid paths.

Algorithm

Define helper(r, c) that returns the minimum path sum from cell (r, c) to the last row.
Base case: if r == n-1, return grid[r][c] (we've reached the last row).
For each column next_col in the next row where next_col != c:
- Recursively compute the path sum and track the minimum.
Return grid[r][c] plus the minimum path sum found.
Try starting from each column in row 0 and return the minimum result.

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)

        def helper(r, c):
            if r == N - 1:
                return grid[r][c]
            res = float("inf")
            for next_col in range(N):
                if c != next_col:
                    res = min(res, grid[r][c] + helper(r + 1, next_col))
            return res

        res = float("inf")
        for c in range(N):
            res = min(res, helper(0, c))
        return res

Time & Space Complexity

Time complexity: $O(n ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same (r, c) states multiple times. By storing computed results in a memoization table, we ensure each state is solved only once. This reduces time complexity from exponential to O(n^3), since for each of the n^2 cells, we may consider up to n transitions.

Algorithm

Create a memo table (dictionary or 2D array) to cache results.
Define helper(r, c) that returns the minimum path sum from (r, c) to the last row.
If (r, c) is already computed, return the cached value.
Base case: if r == n-1, return grid[r][c].
For each next_col != c, recursively compute and track the minimum.
Cache and return grid[r][c] plus the minimum found.
Return the minimum among all starting columns.

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)
        cache = {}

        def helper(r, c):
            if r == N - 1:
                return grid[r][c]
            if (r, c) in cache:
                return cache[(r, c)]

            res = float("inf")
            for next_col in range(N):
                if c != next_col:
                    res = min(res, grid[r][c] + helper(r + 1, next_col))
            cache[(r, c)] = res
            return res

        res = float("inf")
        for c in range(N):
            res = min(res, helper(0, c))
        return res

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

Intuition

We can build the solution iteratively from the last row upward. For each cell, we compute the minimum path sum by considering all columns in the next row except the current one. This bottom-up approach fills a 2D DP table where dp[r][c] represents the minimum path sum from cell (r, c) to any cell in the last row.

Algorithm

Create a 2D DP table initialized to infinity.
Fill the last row: dp[n-1][c] = grid[n-1][c] for all columns.
For each row r from n-2 down to 0:
- For each column c:
  - For each next_col != c:
    - Update dp[r][c] = min(dp[r][c], grid[r][c] + dp[r+1][next_col]).
Return the minimum value in dp[0].

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)
        dp = [[float("inf")] * N for _ in range(N)]

        for c in range(N):
            dp[N - 1][c] = grid[N - 1][c]

        for r in range(N - 2, -1, -1):
            for c in range(N):
                for next_col in range(N):
                    if c != next_col:
                        dp[r][c] = min(dp[r][c], grid[r][c] + dp[r + 1][next_col])

        return min(dp[0])

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

Intuition

Since each row only depends on the next row's values, we can reduce space from O(n^2) to O(n) by using a single 1D array. We process rows from top to bottom, updating the array for each row while referencing the values from the previous iteration.

Algorithm

Initialize DP array with the first row of the grid.
For each subsequent row r:
- Create a new DP array for the current row.
- For each column curr_c:
  - For each prev_c != curr_c, track the minimum from the previous row.
  - Set next_dp[curr_c] = grid[r][curr_c] + min_prev.
- Replace the DP array with the new array.
Return the minimum value in the final DP array.

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)
        dp = grid[0]

        for r in range(1, N):
            next_dp = [float("inf")] * N
            for curr_c in range(N):
                for prev_c in range(N):
                    if prev_c != curr_c:
                        next_dp[curr_c] = min(
                            next_dp[curr_c],
                            grid[r][curr_c] + dp[prev_c]
                        )
            dp = next_dp

        return min(dp)

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n)$

5. Dynamic Programming (Time Optimized)

Intuition

The O(n^3) complexity comes from checking all n columns for each of n^2 cells. We can optimize by observing that when transitioning to a cell, we usually want the minimum from the previous row, unless that minimum is in the same column. So we only need to track the two smallest values from each row: if the current column matches the smallest, use the second smallest; otherwise, use the smallest.

Algorithm

Initialize DP by computing the two smallest (value, index) pairs from the first row.
For each subsequent row:
- For each column, compute the path sum using the smallest previous value if columns differ, else the second smallest.
- Collect all results and find the new two smallest pairs.
Return the minimum value from the final DP.

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        def get_min_two(row):
            two_smallest = []
            for val, idx in row:
                if len(two_smallest) < 2:
                    two_smallest.append((val, idx))
                elif two_smallest[1][0] > val:
                    two_smallest.pop()
                    two_smallest.append((val, idx))
                two_smallest.sort()
            return two_smallest

        N = len(grid)
        first_row = [(val, idx) for idx, val in enumerate(grid[0])]
        dp = get_min_two(first_row)

        for r in range(1, N):
            next_dp = []
            for curr_c in range(N):
                curr_val = grid[r][curr_c]
                min_val = float("inf")
                for prev_val, prev_c in dp:
                    if curr_c != prev_c:
                        min_val = min(min_val, curr_val + prev_val)
                next_dp.append((min_val, curr_c))
            dp = get_min_two(next_dp)

        return min(val for val, idx in dp)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

6. Dynamic Programming (Optimal)

Intuition

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.

Algorithm

Initialize dpIdx1, dpIdx2 (indices of first and second smallest) and dpVal1, dpVal2 (their values) to represent the previous row's state.
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.
After processing all rows, return dpVal1 (the overall minimum).

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

Time & Space Complexity

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

Common Pitfalls

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.