Skip to main content

Minimum Falling Path Sum

Problem Statement​

Given an ( n \times n ) array of integers matrix, return 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. Specifically, the next element from position ((row, col)) will be ((row + 1, col - 1)), ((row + 1, col)), or ((row + 1, col + 1)).

Example 1​

Input:

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

Output:

13

Explanation: There are two falling paths with a minimum sum as shown.

Example 2​

Input:

matrix = [[-19, 57],
[-40, -5]]

Output:

-59

Explanation: The falling path with a minimum sum is shown.

Constraints​

  • n==matrix.length==matrix[i].lengthn == matrix.length == matrix[i].length
  • 1<=n<=1001 <= n <= 100
  • −100<=matrix[i][j]<=100-100 <= matrix[i][j] <= 100

Algorithm​

To solve this problem, we use dynamic programming. The idea is to keep a dp array where dp[i][j] represents the minimum sum of a falling path reaching the element at matrix[i][j].

  1. Initialize the DP table:

    • Create a 2D list dp with the same dimensions as matrix.
    • Initialize the first row of dp with the first row of matrix since the falling path can start from any element in the first row.
  2. Fill the DP table:

    • For each element matrix[i][j] in the subsequent rows:
      • Calculate the minimum sum path to reach matrix[i][j] from the previous row:
        • If j > 0, consider the element from the top-left diagonal dp[i-1][j-1].
        • Consider the element directly above dp[i-1][j].
        • If j < n-1, consider the element from the top-right diagonal dp[i-1][j+1].
      • Update dp[i][j] with the minimum of these values plus matrix[i][j].
  3. Find the minimum falling path sum:

    • The minimum sum of any falling path will be the minimum value in the last row of dp.

Pseudocode​

function minFallingPathSum(matrix):
h = length of matrix
if h == 0:
return 0
w = length of matrix[0]
dp = 2D list of size h x w initialized to infinity
dp[-1] = matrix[-1]

for i from h-2 to 0:
for j from 0 to w-1:
dp[i][j] = matrix[i][j] + min(
dp[i+1][j],
dp[i+1][j-1] if j > 0 else infinity,
dp[i+1][j+1] if j < w-1 else infinity
)

return min(dp[0])

Python Code​

from typing import List

class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
h = len(matrix)
if h == 0:
return 0
w = len(matrix)
dp = [[float('inf')] * w for _ in range(h)]
dp[-1] = matrix[-1]

for i in range(h-2, -1, -1):
for j in range(w):
dp[i][j] = matrix[i][j] + min(
dp[i+1][j],
dp[i+1][j-1] if j > 0 else float("inf"),
dp[i+1][j+1] if j < w-1 else float("inf")
)
return min(dp[0])

Java Code​

class Solution {
public int minFallingPathSum(int[][] matrix) {
int h = matrix.length;
if (h == 0) {
return 0;
}
int w = matrix[0].length;
int[][] dp = new int[h][w];
for (int j = 0; j < w; j++) {
dp[h-1][j] = matrix[h-1][j];
}

for (int i = h - 2; i >= 0; i--) {
for (int j = 0; j < w; j++) {
int down = dp[i+1][j];
int downLeft = (j > 0) ? dp[i+1][j-1] : Integer.MAX_VALUE;
int downRight = (j < w-1) ? dp[i+1][j+1] : Integer.MAX_VALUE;
dp[i][j] = matrix[i][j] + Math.min(down, Math.min(downLeft, downRight));
}
}
int minPathSum = Integer.MAX_VALUE;
for (int j = 0; j < w; j++) {
minPathSum = Math.min(minPathSum, dp[0][j]);
}
return minPathSum;
}
}

C++ Code​

class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int h = matrix.size();
if (h == 0) {
return 0;
}
int w = matrix[0].size();
vector<vector<int>> dp(h, vector<int>(w, INT_MAX));
dp[h-1] = matrix[h-1];

for (int i = h - 2; i >= 0; --i) {
for (int j = 0; j < w; ++j) {
int down = dp[i+1][j];
int downLeft = (j > 0) ? dp[i+1][j-1] : INT_MAX;
int downRight = (j < w-1) ? dp[i+1][j+1] : INT_MAX;
dp[i][j] = matrix[i][j] + min(down, min(downLeft, downRight));
}
}
return *min_element(dp[0].begin(), dp[0].end());
}
};

JavaScript Code​

var minFallingPathSum = function (matrix) {
let h = matrix.length;
if (h === 0) {
return 0;
}
let w = matrix[0].length;
let dp = Array.from({ length: h }, () => Array(w).fill(Infinity));
dp[h - 1] = [...matrix[h - 1]];

for (let i = h - 2; i >= 0; i--) {
for (let j = 0; j < w; j++) {
dp[i][j] =
matrix[i][j] +
Math.min(
dp[i + 1][j],
j > 0 ? dp[i + 1][j - 1] : Infinity,
j < w - 1 ? dp[i + 1][j + 1] : Infinity
);
}
}
return Math.min(...dp[0]);
};