Minimum Failing Path Sum

931.Minimum Falling Path Sum

Array

Dynamic Programming

Matrix

Problem Statement:

Given an n x n matrix of integers, find the minimum sum of any falling path through the 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.

Example:

Input:

matrix = [[2,1,3],[6,5,4],[7,8,9]]

→

Output:

13

Algorithm:

1. Start from bottom row like Triangle problem
2. Create temp array for each row computation
3. Handle three cases: left edge, right edge, middle
4. Find minimum in final row for result

Complexity:

Time: O(n²) | Space: O(n)

Java Solution:

// Exactly like the Triangle Problem
public int minFallingPathSum(int[][] matrix) {
    int[] dp = new int[matrix[0].length];  // Track last row

    // Initialize with bottom row
    for (int j = 0; j < matrix[0].length; j++) 
        dp[j] = matrix[matrix.length - 1][j];
    
    for (int i = matrix.length - 2; i >= 0; i--) {
        // We can use a temp array since we only need last row!!
        // No need for a full matrix
        int[] temp = new int[matrix[0].length];

        for (int j = 0; j < matrix[0].length; j++) {
            if (j == 0)  // Left edge case
                temp[j] = min(dp[0], dp[1]) + matrix[i][j];
            else if (j == matrix[0].length - 1)  // Right edge case
                temp[j] = min(dp[j], dp[j - 1]) + matrix[i][j];
            else  // Middle elements
                temp[j] = min(dp[j - 1], dp[j], dp[j + 1]) + matrix[i][j];
        }

        dp = temp;  // Update dp to current row
    }  

    // Find minimum in final row
    int min = Integer.MAX_VALUE;
    for (int j = 0; j < dp.length; j++) 
        min = Math.min(dp[j], min);

    return min;
}

public int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

public int min(int a, int b) {
    return Math.min(a, b);
}

Python Solution:

def minFallingPathSum(self, matrix: List[List[int]]) -> int:
    n = len(matrix)
    dp = matrix[-1][:]  # Start with bottom row
    
    for i in range(n - 2, -1, -1):
        temp = [0] * n  # Temp array for current row
        
        for j in range(n):
            if j == 0:  # Left edge
                temp[j] = min(dp[0], dp[1]) + matrix[i][j]
            elif j == n - 1:  # Right edge
                temp[j] = min(dp[j], dp[j-1]) + matrix[i][j]
            else:  # Middle elements
                temp[j] = min(dp[j-1], dp[j], dp[j+1]) + matrix[i][j]
                
        dp = temp  # Update dp for next row
    
    return min(dp)

C++ Solution:

class Solution {
public:
    int minFallingPathSum(vectorint>>& matrix) {
        int n = matrix.size();
        vector<int> dp = matrix[n-1];  // Start with bottom row
        
        for(int i = n-2; i >= 0; i--) {
            vector<int> temp(n);  // Temp array for current row
            
            for(int j = 0; j < n; j++) {
                if(j == 0)  // Left edge
                    temp[j] = min({dp[0], dp[1]}) + matrix[i][j];
                else if(j == n-1)  // Right edge
                    temp[j] = min({dp[j], dp[j-1]}) + matrix[i][j];
                else  // Middle elements
                    temp[j] = min({dp[j-1], dp[j], dp[j+1]}) + matrix[i][j];
            }
            
            dp = temp;  // Update dp for next row
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};