LeetCode Solutions Blog

Minimum Falling Path Sum II

Number: 1224

Difficulty: Hard

Paid? No

Problem Description

Given an n x n integer matrix, return the minimum sum of a falling path with non-zero shifts. A falling path picks exactly one element from each row such that no two adjacent rows pick an element from the same column.

Key Insights

Use dynamic programming to compute the minimum falling path sum row by row.
Instead of checking all columns in the previous row for every cell, track the smallest and second smallest sums from the previous row.
If the current cell's column is the same as the column with the smallest previous sum, use the second smallest; otherwise, use the smallest.
This optimization reduces the inner loop computation and improves efficiency.
Handle the edge case when the matrix size is 1.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n) if using a one-dimensional DP array (can also be done in-place)

Solution

We use a dynamic programming approach where dp[i][j] represents the minimum sum of a falling path ending in cell (i, j) in row i. For each row i, we compute two values from the previous row: the smallest sum (min1) and the second smallest sum (min2) along with their column indices. For the current cell, if its column is the same as the column of min1, then we add min2 from the previous row; otherwise, we add min1. This avoids the need to iterate over all columns for each cell when updating the current row, leading to significant optimization for larger matrices.

Code Solutions

# Function to calculate the minimum falling path sum
def minFallingPathSum(grid):
    n = len(grid)
    # base case: if grid has only one row, return the only element
    if n == 1:
        return grid[0][0]
    
    # dp will hold the minimum sum for each column for the current row
    dp = grid[0][:]

    # Process each row starting from the second row
    for i in range(1, n):
        # Initialize variables to find the smallest and second smallest in dp
        min1 = float('inf')
        min2 = float('inf')
        index_min1 = -1
        
        # Find the smallest and second smallest value in the current dp
        for j in range(n):
            if dp[j] < min1:
                min2 = min1
                min1 = dp[j]
                index_min1 = j
            elif dp[j] < min2:
                min2 = dp[j]
        
        # Temp array for current row's dp values
        new_dp = [0] * n
        for j in range(n):
            # if current column matches index of min1, use min2 from previous row, otherwise use min1
            if j == index_min1:
                new_dp[j] = grid[i][j] + min2
            else:
                new_dp[j] = grid[i][j] + min1
        dp = new_dp  # update dp for the next iteration

    # Return the minimum value in dp after processing all rows
    return min(dp)

# Example usage:
print(minFallingPathSum([[1,2,3],[4,5,6],[7,8,9]]))  # Output should be 13