We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Falling Path Sum

Difficulty: Medium

Problem Description

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right.

Key Insights

  • A falling path can be initiated from any element in the first row of the matrix.
  • The movement to the next row can be directly downward or diagonally (left or right).
  • Dynamic programming can be used to build up the minimum path sums from the bottom of the matrix to the top.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (in-place modification of the input matrix)

Solution

To solve the problem, we will use a dynamic programming approach. The idea is to modify the input matrix in place, where each element at position (i, j) will store the minimum sum of the falling path that ends at that position. We will iterate from the second-to-last row up to the first row, updating each element based on the minimum values from the row directly below it, considering the possible positions we can fall from (directly below, below left, and below right). Finally, the minimum value in the first row will give us the answer.

Code Solutions

def minFallingPathSum(matrix):
    n = len(matrix)
    for i in range(n - 2, -1, -1):
        for j in range(n):
            # Consider the three possible paths to the current cell
            below = matrix[i + 1][j]  # directly below
            below_left = matrix[i + 1][j - 1] if j > 0 else float('inf')  # below left
            below_right = matrix[i + 1][j + 1] if j < n - 1 else float('inf')  # below right
            
            # Update the current cell with the minimum falling path sum
            matrix[i][j] += min(below, below_left, below_right)
    
    # The answer is the minimum value in the first row
    return min(matrix[0])
← Back to All Questions