Minimum Falling Path Sum — Solution in Python, Java & C++
Minimum Falling Path Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Falling Path Sum is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Bloomberg and Dream11 interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google, Bloomberg, Dream11
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an n × n array of integers matrix, return the minimum sum of any falling path through it.
A falling path picks one element from each row, and consecutive picks must be in the same column or in a column differing by one.
Example 1
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: One minimum path is 1 → 5 → 7.
Example 2
Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Example 3
Input: matrix = [[7]]
Output: 7
Constraints
1 <= matrix.length <= 8matrix[i].length == matrix.length-100 <= matrix[i][j] <= 100
Hints for Minimum Falling Path Sum
Hint 1
Process the rows top to bottom, keeping the best cost to reach each column of the current row.
Hint 2
A cell can be reached from directly above or from either diagonal, so take the minimum of those three.
Hint 3
Only the previous row matters — one array of length
nsuffices.
How to solve Minimum Falling Path Sum
Process rows top to bottom keeping the cheapest cost to reach each column; each cell takes the min of the three cells above it (up, up-left, up-right).
Approach
- Start
dp = matrix[0]. - For each following row,
nxt[c] = matrix[r][c] + min(dp[c-1], dp[c], dp[c+1])with bounds respected. - Return
min(dp).
Why it works
A falling path enters each cell from one of exactly three predecessors, so the best cost decomposes over that choice and only the previous row is needed.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Take the minimum over the whole last row — the path may end anywhere.
Reference solution
Python
def minFallingPathSum(matrix) -> int:
n = len(matrix)
dp = list(matrix[0])
for r in range(1, n):
nxt = []
for c in range(n):
best = dp[c]
if c > 0:
best = min(best, dp[c - 1])
if c + 1 < n:
best = min(best, dp[c + 1])
nxt.append(matrix[r][c] + best)
dp = nxt
return min(dp)Java
public static int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int[] dp = Arrays.copyOf(matrix[0], n);
for (int r = 1; r < n; r++) {
int[] next = new int[n];
for (int c = 0; c < n; c++) {
int best = dp[c];
if (c > 0) best = Math.min(best, dp[c - 1]);
if (c + 1 < n) best = Math.min(best, dp[c + 1]);
next[c] = matrix[r][c] + best;
}
dp = next;
}
int answer = dp[0];
for (int c = 1; c < n; c++) answer = Math.min(answer, dp[c]);
return answer;
}C++
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = (int) matrix.size();
vector<int> dp = matrix[0];
for (int r = 1; r < n; r++) {
vector<int> next(n, 0);
for (int c = 0; c < n; c++) {
int best = dp[c];
if (c > 0) best = min(best, dp[c - 1]);
if (c + 1 < n) best = min(best, dp[c + 1]);
next[c] = matrix[r][c] + best;
}
dp = next;
}
return *min_element(dp.begin(), dp.end());
}JavaScript
var minFallingPathSum = function(matrix) {
const n = matrix.length;
let dp = matrix[0].slice();
for (let r = 1; r < n; r++) {
const next = [];
for (let c = 0; c < n; c++) {
let best = dp[c];
if (c > 0 && dp[c - 1] < best) best = dp[c - 1];
if (c + 1 < n && dp[c + 1] < best) best = dp[c + 1];
next.push(matrix[r][c] + best);
}
dp = next;
}
let answer = dp[0];
for (let c = 1; c < n; c++) {
if (dp[c] < answer) answer = dp[c];
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming