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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Falling Path Sum

Number: 967

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Bloomberg, Uber, Goldman Sachs

Problem Description

Given an n x n matrix of integers, we must find the minimum sum of any falling path. A falling path starts at any element in the first row and moves to the next row choosing an element directly below or diagonally left/right.

Key Insights

  • Use dynamic programming to calculate the minimum path sum from bottom to top.
  • For each cell, only consider the three possible moves in the next row (down, down-left, down-right), making sure to handle boundary conditions.
  • A bottom-up approach allows us to build the solution by using the already computed results of the subproblems.
  • The final result is the minimum value in the computed first row.

Space and Time Complexity

Time Complexity: O(n^2) because each of the n*n elements is processed once. Space Complexity: O(n^2) using an auxiliary DP matrix, though the solution can be optimized to O(1) extra space by updating the matrix in-place.

Solution

We solve this problem using dynamic programming with a bottom-up approach. We initialize a DP structure (or update the matrix in-place) that stores the minimum falling path sum from each cell to the bottom row. Starting from the second last row, we iterate upward. For each cell (i, j), we add the current cell value with the minimum of the allowed moves from the row below (directly below, diagonally left, and diagonally right). Consider boundary conditions for the first and last columns. The answer is the minimum value found in the top row after processing.

Code Solutions

# Python solution with line-by-line comments

def minFallingPathSum(matrix):
    # Get the dimension of the matrix
    n = len(matrix)
    
    # Process the matrix from second last row to the first row
    for row in range(n - 2, -1, -1):
        for col in range(n):
            # Initialize the minimum sum from the next row as a large number.
            best_below = matrix[row + 1][col]
            # Check the diagonal left if it is within bounds
            if col - 1 >= 0:
                best_below = min(best_below, matrix[row + 1][col - 1])
            # Check the diagonal right if it is within bounds
            if col + 1 < n:
                best_below = min(best_below, matrix[row + 1][col + 1])
            # Update the current cell with the sum of its value and the best move below
            matrix[row][col] += best_below
    
    # The result is the minimum value in the first row after processing
    return min(matrix[0])

# Example usage:
matrix = [[2,1,3],[6,5,4],[7,8,9]]
print(minFallingPathSum(matrix))  # Expected output: 13
← Back to All Questions