LeetCode 1289 - Minimum Falling Path Sum II

The problem asks us to compute the minimum sum of a falling path with non-zero shifts in a square n x n matrix. A fallin

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 1289

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem asks us to compute the minimum sum of a falling path with non-zero shifts in a square n x n matrix. A falling path is formed by selecting exactly one element from each row, with the constraint that no two consecutive elements are from the same column. Essentially, as you move down the rows, the column of your selection must change.

The input grid is a 2D integer array representing the matrix. The expected output is a single integer representing the smallest possible sum achievable under the non-zero shift condition.

Constraints indicate that n can be as large as 200 and element values range from -99 to 99. This means brute-force enumeration of all possible paths will be too slow because the number of potential paths is n^(n). The problem guarantees at least one element per row, so we do not need to handle empty matrices. Edge cases that could cause naive approaches to fail include matrices with negative values, matrices where all elements are the same, or single-row matrices.

Approaches

A brute-force approach would involve generating all possible paths by recursively exploring each choice in each row while avoiding the column from the previous row. This guarantees correctness but is exponential in complexity (O(n^n)) and therefore infeasible for n up to 200.

The key insight for an optimal solution is dynamic programming with row-wise state compression. For each row, we can compute the minimum falling path sum ending in each column by considering the minimum sums from the previous row in all other columns. A further optimization is to track the smallest and second smallest values from the previous row, which allows us to compute the minimum for the current cell in O(1) per cell instead of scanning all columns.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^n) O(n) Recursively explore all paths with column constraints
Optimal DP with Min Tracking O(n^2) O(n) Use previous row minimums to update current row efficiently

Algorithm Walkthrough

  1. Initialize a 1D array dp to store the minimum path sums ending at each column of the first row. This is simply the values of the first row.
  2. For each subsequent row, determine the smallest (min1) and second smallest (min2) values from the dp of the previous row, along with the column index of min1.
  3. For each column j in the current row, update the new DP value as grid[i][j] + (min1 if j != min1_index else min2). This ensures we do not reuse the same column from the previous row.
  4. After processing the row, replace dp with the new row's computed values.
  5. After iterating through all rows, the result is the minimum value in the final dp.

Why it works: By always carrying the minimum and second minimum from the previous row, we guarantee that each cell picks the smallest possible sum from the previous row while respecting the non-zero shift constraint. This ensures optimality at each step and leads to a globally minimal sum.

Python Solution

from typing import List

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = grid[0][:]  # Initialize with the first row
        
        for i in range(1, n):
            new_dp = [0] * n
            # Find the smallest and second smallest in the previous row
            min1 = min2 = float('inf')
            min1_index = -1
            for j in range(n):
                if dp[j] < min1:
                    min2 = min1
                    min1 = dp[j]
                    min1_index = j
                elif dp[j] < min2:
                    min2 = dp[j]
            
            for j in range(n):
                new_dp[j] = grid[i][j] + (min1 if j != min1_index else min2)
            
            dp = new_dp
        
        return min(dp)

This implementation first copies the first row into dp. For each row, it computes the smallest and second smallest sums from the previous row. Each element in the new row is updated by adding the corresponding grid value to the correct minimum. This avoids reusing the same column in adjacent rows. Finally, it returns the minimum from the last row.

Go Solution

func minFallingPathSum(grid [][]int) int {
    n := len(grid)
    dp := make([]int, n)
    copy(dp, grid[0])
    
    for i := 1; i < n; i++ {
        newDP := make([]int, n)
        min1, min2 := int(1e9), int(1e9)
        min1Index := -1
        
        for j := 0; j < n; j++ {
            if dp[j] < min1 {
                min2 = min1
                min1 = dp[j]
                min1Index = j
            } else if dp[j] < min2 {
                min2 = dp[j]
            }
        }
        
        for j := 0; j < n; j++ {
            if j != min1Index {
                newDP[j] = grid[i][j] + min1
            } else {
                newDP[j] = grid[i][j] + min2
            }
        }
        dp = newDP
    }
    
    result := dp[0]
    for _, val := range dp {
        if val < result {
            result = val
        }
    }
    return result
}

In Go, we use slices instead of lists and manually track indices for minimums. We use a large number 1e9 as an initial comparison for min1 and min2. Copying the first row into dp ensures correct initialization.

Worked Examples

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

Initial dp: [1,2,3]

Row 1 processing: min1=1 (index 0), min2=2

New dp: [4+2=6, 5+1=6, 6+1=7] → [6,6,7]

Row 2 processing: min1=6 (index 0), min2=6

New dp: [7+6=13, 8+6=14, 9+6=13] → [13,14,13]

Final result: min([13,14,13]) = 13

Example 2: grid = [[7]]

Only one row, result = 7

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) For each of n rows, we process n columns, finding min1 and min2 in O(n)
Space O(n) We only keep one DP array for the previous row and one for the current row

The optimization of tracking two minimums avoids O(n^3) behavior that would occur if we scanned all previous row elements for each column.

Test Cases

# Provided examples
assert Solution().minFallingPathSum([[1,2,3],[4,5,6],[7,8,9]]) == 13  # example 1
assert Solution().minFallingPathSum([[7]]) == 7  # example 2

# Boundary tests
assert Solution().minFallingPathSum([[1]]) == 1  # single element
assert Solution().minFallingPathSum([[1,2],[3,4]]) == 5  # small 2x2 grid

# Negative numbers
assert Solution().minFallingPathSum([[-1,-2],[-3,-4]]) == -5

# Large uniform grid
assert Solution().minFallingPathSum([[1]*200]*200) == 200  # all ones
Test Why
[[1,2,3],[4,5,6],[7,8,9]] Typical 3x3 grid with distinct values
[[7]] Single element matrix edge case
[[1]] Minimal grid size
[[1,2],[3,4]] Small grid for correctness verification
[[-1,-2],[-3,-4]] Negative values to test sum calculation
[[1]*200]*200 Large uniform grid to stress test performance

Edge Cases

One important edge case is a single-element matrix, where the algorithm must correctly return that element without accessing out-of-bounds indices. Our DP initialization handles this naturally.

Another edge case involves rows where the minimum occurs in multiple columns, which can affect the choice between the smallest and second smallest. Tracking the indices ensures that the same column is never reused, even when values are duplicated.

A third edge case is negative numbers, where summing could decrease the total. The algorithm correctly handles negative values because the dynamic programming updates do not assume positivity; the minimums are determined by actual sums rather than absolute values.