Minimum Falling Path Sum
find minimum sum while coming down in a grid, you can either go down , or down left or down right
Minimum Falling Path Sum
Problem Statement
Given an n x 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 at each step, moves to the element in the next row that is either directly below, or diagonally left/right. Specifically, from position (row, col), the next step can go to (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).
Examples
Example 1
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths that both produce this minimum sum.
Example 2
Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with the minimum sum is shown.
Solution
Brute Force
For every possible starting column in the first row, we trace downward through all the possible paths, and find the minimum sum among them.
- At each cell, we try the three possible moves to the next row (down-left, down, down-right), and take whichever leads to the smallest total.
- If a move would go out of bounds (off the left or right edge of the matrix), we treat that option as
Infinity, so it never gets chosen. - The base case is the last row, where a cell's value is simply itself.
var minFallingPathSum = function (matrix) {
let m = matrix.length;
let n = matrix[0].length;
let minimum = Infinity;
function recurr(i, j) {
if (j < 0 || j >= n) {
return Infinity;
}
if (i === m - 1) {
return matrix[i][j];
}
let downLeft = recurr(i + 1, j - 1);
let down = recurr(i + 1, j);
let dowRight = recurr(i + 1, j + 1);
const bestNext = Math.min(downLeft, down, dowRight);
return matrix[i][j] + bestNext;
}
let answer = Infinity;
for (let col = 0; col < n; col++) {
let pathSum = recurr(0, col);
answer = Math.min(pathSum, answer);
}
return answer;
};
Memoization (Top-Down)
Same approach as the brute force version, but we store each cell's result the first time we calculate it, so we never recompute the same path twice.
var minFallingPathSum = function (matrix) {
let m = matrix.length;
let n = matrix[0].length;
let minimum = Infinity;
function recurr(i, j, dp) {
if (j < 0 || j >= n) {
return Infinity;
}
if (dp[i][j] !== undefined) {
return dp[i][j];
}
if (i === m - 1) {
return matrix[i][j];
}
let downLeft = recurr(i + 1, j - 1, dp);
let down = recurr(i + 1, j, dp);
let dowRight = recurr(i + 1, j + 1, dp);
const bestNext = Math.min(downLeft, down, dowRight);
dp[i][j] = matrix[i][j] + bestNext;
return dp[i][j];
}
let dp = Array.from({ length: m }, () => Array(n).fill(undefined));
let answer = Infinity;
for (let col = 0; col < n; col++) {
let pathSum = recurr(0, col, dp);
answer = Math.min(pathSum, answer);
}
return answer;
};
Tabulation (Bottom-Up)
This version builds the answer going forward, starting from the first row and working down, rather than starting from the end and recursing backward.
- For the first row, each cell's value in
dpis simply its own value inmatrix. - For every other row, each cell looks at the three cells above it (up-left, up, up-right) from the previous row, and adds the smallest of those to its own value.
- If a cell is at the left edge or right edge of the matrix, the missing diagonal neighbor is treated as an extremely large number (
1e9), so it's never mistakenly chosen as the minimum. - At the end, the answer is the smallest value found anywhere in the last row of
dp.
/**
* @param {number[][]} matrix
* @return {number}
*/
var minFallingPathSum = function (matrix) {
let m = matrix.length;
let n = matrix[0].length;
let dp = Array.from(
{ length: m },
() => Array(n).fill(0)
);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// First row
if (i === 0) {
dp[i][j] = matrix[i][j];
}
else {
// Up-left
let upLeft = matrix[i][j];
if (j > 0) {
upLeft += dp[i - 1][j - 1];
} else {
upLeft += 1e9;
}
// Up
let up = matrix[i][j] + dp[i - 1][j];
// Up-right
let upRight = matrix[i][j];
if (j < n - 1) {
upRight += dp[i - 1][j + 1];
} else {
upRight += 1e9;
}
dp[i][j] = Math.min(
upLeft,
up,
upRight
);
}
}
}
return Math.min(...dp[m - 1]);
};