Minimum Falling Path Sum

Problem

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. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Examples

Example 1:

1
2
3
4
5


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:

1
2
3
4
5


Input:
matrix = [[-19,57],[-40,-5]]
Output:
 -59
Explanation: The falling path with a minimum sum is shown.

Solution

Method 1 – Dynamic Programming

Intuition

We use dynamic programming to compute the minimum falling path sum for each cell by considering the three possible cells above it. We build up the solution row by row.

Approach

For each cell in the matrix, starting from the second row, update its value by adding the minimum of the three possible cells above (directly above, above-left, above-right).
The answer is the minimum value in the last row after processing all rows.

Recurrence Relation:

Let dp[i][j] be the minimum falling path sum to cell (i, j).

1
2
3
4
5


dp[i][j] = matrix[i][j] + min(
	dp[i-1][j],
	dp[i-1][j-1] if j > 0,
	dp[i-1][j+1] if j < n-1
)

Base Case:

dp[0][j] = matrix[0][j] for all columns in the first row.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
	int minFallingPathSum(vector<vector<int>>& matrix) {
		int n = matrix.size();
		vector<vector<int>> dp = matrix;
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				int minAbove = dp[i-1][j];
				if (j > 0) minAbove = min(minAbove, dp[i-1][j-1]);
				if (j < n-1) minAbove = min(minAbove, dp[i-1][j+1]);
				dp[i][j] += minAbove;
			}
		}
		return *min_element(dp[n-1].begin(), dp[n-1].end());
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		copy(dp[i], matrix[i])
	}
	for i := 1; i < n; i++ {
		for j := 0; j < n; j++ {
			minAbove := dp[i-1][j]
			if j > 0 && dp[i-1][j-1] < minAbove {
				minAbove = dp[i-1][j-1]
			}
			if j < n-1 && dp[i-1][j+1] < minAbove {
				minAbove = dp[i-1][j+1]
			}
			dp[i][j] += minAbove
		}
	}
	ans := dp[n-1][0]
	for _, v := range dp[n-1] {
		if v < ans {
			ans = v
		}
	}
	return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
	public int minFallingPathSum(int[][] matrix) {
		int n = matrix.length;
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++)
			dp[0][i] = matrix[0][i];
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int minAbove = dp[i-1][j];
				if (j > 0) minAbove = Math.min(minAbove, dp[i-1][j-1]);
				if (j < n-1) minAbove = Math.min(minAbove, dp[i-1][j+1]);
				dp[i][j] = matrix[i][j] + minAbove;
			}
		}
		int ans = dp[n-1][0];
		for (int v : dp[n-1]) ans = Math.min(ans, v);
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
	fun minFallingPathSum(matrix: Array<IntArray>): Int {
		val n = matrix.size
		val dp = Array(n) { matrix[it].clone() }
		for (i in 1 until n) {
			for (j in 0 until n) {
				var minAbove = dp[i-1][j]
				if (j > 0) minAbove = minOf(minAbove, dp[i-1][j-1])
				if (j < n-1) minAbove = minOf(minAbove, dp[i-1][j+1])
				dp[i][j] += minAbove
			}
		}
		return dp[n-1].minOrNull() ?: 0
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


from typing import List
class Solution:
	def minFallingPathSum(self, matrix: List[List[int]]) -> int:
		n = len(matrix)
		dp = [row[:] for row in matrix]
		for i in range(1, n):
			for j in range(n):
				min_above = dp[i-1][j]
				if j > 0:
					min_above = min(min_above, dp[i-1][j-1])
				if j < n-1:
					min_above = min(min_above, dp[i-1][j+1])
				dp[i][j] += min_above
		return min(dp[n-1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
	pub fn min_falling_path_sum(matrix: Vec<Vec<i32>>) -> i32 {
		let n = matrix.len();
		let mut dp = matrix.clone();
		for i in 1..n {
			for j in 0..n {
				let mut min_above = dp[i-1][j];
				if j > 0 {
					min_above = min_above.min(dp[i-1][j-1]);
				}
				if j < n-1 {
					min_above = min_above.min(dp[i-1][j+1]);
				}
				dp[i][j] += min_above;
			}
		}
		*dp[n-1].iter().min().unwrap()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
	minFallingPathSum(matrix: number[][]): number {
		const n = matrix.length;
		const dp = matrix.map(row => [...row]);
		for (let i = 1; i < n; i++) {
			for (let j = 0; j < n; j++) {
				let minAbove = dp[i-1][j];
				if (j > 0) minAbove = Math.min(minAbove, dp[i-1][j-1]);
				if (j < n-1) minAbove = Math.min(minAbove, dp[i-1][j+1]);
				dp[i][j] += minAbove;
			}
		}
		return Math.min(...dp[n-1]);
	}
}

Complexity

⏰ Time complexity: O(n^2) — We process each cell in the matrix once.
🧺 Space complexity: O(n^2) — DP table of size n x n is used.

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#