Minimum Falling Path Sum solution and explanation
Google
9 more videos on this problem
Minimum Falling Path Sum | Recursion | Memo | Bottom Up | Leetcode 931codestorywithMIK · 48:56 · 18K views
Minimum Falling Path Sum - Leetcode 931 - PythonNeetCodeIO · 14:02 · 17K views
Leetcode 931 - Dynamic Programming | Min Falling Path SumNideesh Terapalli · 6:17 · 7K views
Minimum Falling Path Sum | Leetcode 931 | HindiCodebix · 15:31 · 5K views
931. Minimum Falling Path Sum | LEETCODE MEDIUM | DYNAMIC PROGRAMMINGcode Explainer · 9:05 · 4K views
931. Minimum Falling Path Sum | Recursion - DP - DP OptimisedAryan Mittal · 14:49 · 2K views
[Java] Leetcode 931. Minimum Falling Path Sum [DP Min/Max Path to Target #6]Eric Programming · 12:09 · 2K views
Leetcode 931 Minimum Falling Path Sum | Coding Decoded SDE SheetCoding Decoded · 6:14 · 793 views
931. Minimum Falling Path Sum | JavaScript | Iteration | Simple | Easy Solution | MemoizationLeetCodeWithMonu · 17:00 · 439 views
12. Minimum Falling Path Sum | LeetCode Medium 931| Dynamic ProgrammingAceCoder Academy · 16:59 · 286 views
The 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).
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].length1 <= n <= 100-100 <= matrix[i][j] <= 100
Approach overview
Problem Overview: You are given an n x n matrix of integers. A falling path starts at any cell in the first row and moves to the next row either directly below, diagonally left, or diagonally right. The goal is to compute the minimum possible sum of values along any valid falling path from the top row to the bottom row.
Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))
This approach models the problem as recursion over rows. For each cell (r, c), recursively compute the minimum path sum starting from that cell by exploring the three valid next positions: (r+1, c-1), (r+1, c), and (r+1, c+1). Many subproblems repeat, so store results in a memo table to avoid recomputation. Each cell is solved once, which reduces exponential recursion to quadratic time. This method is intuitive if you think in terms of exploring all paths but caching results.
The recursion stops when the last row is reached. Out-of-bound column moves are ignored. Because every matrix cell is computed once and stored, the complexity becomes O(n^2). This pattern is common in dynamic programming problems on grids.
Approach 2: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n^2) or O(1) in-place)
The bottom-up strategy processes the matrix row by row. Starting from the second row, update each cell by adding the minimum of the three reachable cells from the previous row: up-left, up, and up-right. This converts the matrix into a DP table where each entry represents the minimum path sum reaching that cell.
For cell (r, c), compute matrix[r][c] += min(prev[c], prev[c-1], prev[c+1]) while handling boundary columns carefully. After processing all rows, the answer is the minimum value in the last row. This method iterates once over the grid and avoids recursion overhead. Because the DP values can overwrite the original matrix, the extra space can be reduced to O(1).
This technique is typical for problems involving transitions in a matrix or grid where each state depends on nearby cells. Iterating through the array structure row by row keeps the implementation simple and efficient.
Recommended for interviews: Bottom-up dynamic programming is the expected solution. It demonstrates that you can convert recursive state transitions into iterative DP and optimize space if needed. Showing the top-down memoized version first can help explain the recurrence, but the bottom-up implementation signals stronger DP problem-solving skills.
Approach 1: Bottom-Up Dynamic Programming Approach
Using a dynamic programming matrix, you can start from the second-last row of the matrix and calculate the minimum path sum by traversing through possible paths (directly below, diagonally left, and diagonally right). Update the matrix in-place to use constant space.
class Solution:
def minFallingPathSum(self, matrix):
n = len(matrix)
for i in range(n-2, -1, -1):
for j in range(n):
best = matrix[i+1][j]
if j > 0:
best = min(best, matrix[i+1][j-1])
if j < n-1:
best = min(best, matrix[i+1][j+1])
matrix[i][j] += best
return min(matrix[0])class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
int best = matrix[i + 1][j];
if (j > 0) best = Math.min(best, matrix[i + 1][j - 1]);
if (j < n - 1) best = Math.min(best, matrix[i + 1][j + 1]);
matrix[i][j] += best;
}
}
int minSum = Integer.MAX_VALUE;
for (int val : matrix[0]) {
minSum = Math.min(minSum, val);
}
return minSum;
}
}#include <vector>
#include <algorithm>
using namespace std;
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
int mn = matrix[i + 1][j];
if (j > 0) mn = min(mn, matrix[i + 1][j - 1]);
if (j < n - 1) mn = min(mn, matrix[i + 1][j + 1]);
matrix[i][j] += mn;
}
}
return *min_element(matrix[0].begin(), matrix[0].end());
}var minFallingPathSum = function(matrix) {
const n = matrix.length;
for (let i = n - 2; i >= 0; i--) {
for (let j = 0; j < n; j++) {
let best = matrix[i + 1][j];
if (j > 0) best = Math.min(best, matrix[i + 1][j - 1]);
if (j < n - 1) best = Math.min(best, matrix[i + 1][j + 1]);
matrix[i][j] += best;
}
}
return Math.min(...matrix[0]);
};#include <stdio.h>
#include <limits.h>
int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize) {
for (int row = matrixSize - 2; row >= 0; row--) {
for (int col = 0; col < matrixColSize[row]; col++) {
int best = matrix[row + 1][col];
if (col > 0) {
best = (best < matrix[row + 1][col - 1]) ? best : matrix[row + 1][col - 1];
}
if (col < matrixColSize[row + 1] - 1) {
best = (best < matrix[row + 1][col + 1]) ? best : matrix[row + 1][col + 1];
}
matrix[row][col] += best;
}
}
int minSum = INT_MAX;
for (int i = 0; i < matrixColSize[0]; i++) {
if(matrix[0][i] < minSum) {
minSum = matrix[0][i];
}
}
return minSum;
}public class Solution {
public int MinFallingPathSum(int[][] matrix) {
int n = matrix.Length;
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
int best = matrix[i + 1][j];
if (j > 0) best = Math.Min(best, matrix[i + 1][j - 1]);
if (j < n - 1) best = Math.Min(best, matrix[i + 1][j + 1]);
matrix[i][j] += best;
}
}
int minSum = int.MaxValue;
foreach (int val in matrix[0]) {
minSum = Math.Min(minSum, val);
}
return minSum;
}
}This Python solution modifies the matrix in place to track minimal paths as it calculates from the bottom to the top row.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Top-Down Dynamic Programming with Memoization
For this approach, we use recursion with memoization to explore paths starting from the first row to the last row. We store intermediate results to avoid redundant calculations.
class Solution:
def minFallingPathSum(self, matrix):
n = len(matrix)
memo = [[float('inf')] * n for _ in range(n)]
def dfs(row, col):
if row == n:
return 0
if memo[row][col] != float('inf'):
return memo[row][col]
res = matrix[row][col] + dfs(row + 1, col)
if col > 0:
res = min(res, matrix[row][col] + dfs(row + 1, col - 1))
if col < n - 1:
res = min(res, matrix[row][col] + dfs(row + 1, col + 1))
memo[row][col] = res
return res
minSum = float('inf')
for col in range(n):
minSum = min(minSum, dfs(0, col))
return minSumimport java.util.Arrays;
class Solution {
private int[][] memo;
private int dfs(int[][] matrix, int row, int col) {
int n = matrix.length;
if (row == n) return 0;
if (memo[row][col] != Integer.MAX_VALUE) return memo[row][col];
int res = matrix[row][col] + dfs(matrix, row + 1, col);
if (col > 0) res = Math.min(res, matrix[row][col] + dfs(matrix, row + 1, col - 1));
if (col < n - 1) res = Math.min(res, matrix[row][col] + dfs(matrix, row + 1, col + 1));
return memo[row][col] = res;
}
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
memo = new int[n][n];
for (int[] row : memo) {
Arrays.fill(row, Integer.MAX_VALUE);
}
int minSum = Integer.MAX_VALUE;
for (int col = 0; col < n; col++) {
minSum = Math.min(minSum, dfs(matrix, 0, col));
}
return minSum;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> memo;
int dfs(vector<vector<int>>& matrix, int row, int col) {
int n = matrix.size();
if (row == n) return 0;
if (memo[row][col] != INT_MAX) return memo[row][col];
int res = matrix[row][col] + dfs(matrix, row + 1, col);
if (col > 0) res = min(res, matrix[row][col] + dfs(matrix, row + 1, col - 1));
if (col < n - 1) res = min(res, matrix[row][col] + dfs(matrix, row + 1, col + 1));
return memo[row][col] = res;
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
memo.assign(n, vector<int>(n, INT_MAX));
int minSum = INT_MAX;
for (int col = 0; col < n; ++col) {
minSum = min(minSum, dfs(matrix, 0, col));
}
return minSum;
}var minFallingPathSum = function(matrix) {
const n = matrix.length;
const memo = Array.from({ length: n }, () => Array(n).fill(Infinity));
const dfs = (row, col) => {
if (row === n) return 0;
if (memo[row][col] !== Infinity) return memo[row][col];
let minSum = matrix[row][col] + dfs(row + 1, col);
if (col > 0) minSum = Math.min(minSum, matrix[row][col] + dfs(row + 1, col - 1));
if (col < n - 1) minSum = Math.min(minSum, matrix[row][col] + dfs(row + 1, col + 1));
memo[row][col] = minSum;
return minSum;
};
let minPathSum = Infinity;
for (let col = 0; col < n; col++) {
minPathSum = Math.min(minPathSum, dfs(0, col));
}
return minPathSum;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
int min(int a, int b) { return (a < b) ? a : b; }
int dfs(int** matrix, int row, int col, int n, int** memo) {
if (row == n) return 0;
if (memo[row][col] != INT_MAX) return memo[row][col];
int res = INT_MAX;
res = min(res, matrix[row][col] + dfs(matrix, row + 1, col, n, memo));
if (col > 0) res = min(res, matrix[row][col] + dfs(matrix, row + 1, col - 1, n, memo));
if (col < n - 1) res = min(res, matrix[row][col] + dfs(matrix, row + 1, col + 1, n, memo));
memo[row][col] = res;
return res;
}
int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize) {
int** memo = (int**)malloc(sizeof(int*) * matrixSize);
for (int i = 0; i < matrixSize; i++) {
memo[i] = (int*)malloc(sizeof(int) * (*matrixColSize));
for (int j = 0; j < *matrixColSize; j++) {
memo[i][j] = INT_MAX;
}
}
int minSum = INT_MAX;
for (int col = 0; col < *matrixColSize; col++) {
minSum = min(minSum, dfs(matrix, 0, col, matrixSize, memo));
}
for (int i = 0; i < matrixSize; i++) free(memo[i]);
free(memo);
return minSum;
}public class Solution {
private int[][] memo;
public int MinFallingPathSum(int[][] matrix) {
int n = matrix.Length;
memo = new int[n][];
for (int i = 0; i < n; i++) {
memo[i] = new int[n];
for (int j = 0; j < n; j++) {
memo[i][j] = int.MaxValue;
}
}
int minSum = int.MaxValue;
for (int col = 0; col < n; col++) {
minSum = Math.Min(minSum, Dfs(matrix, 0, col));
}
return minSum;
}
private int Dfs(int[][] matrix, int row, int col) {
int n = matrix.Length;
if (row == n) return 0;
if (memo[row][col] != int.MaxValue) return memo[row][col];
int res = matrix[row][col] + Dfs(matrix, row + 1, col);
if (col > 0) res = Math.Min(res, matrix[row][col] + Dfs(matrix, row + 1, col - 1));
if (col < n - 1) res = Math.Min(res, matrix[row][col] + Dfs(matrix, row + 1, col + 1));
memo[row][col] = res;
return res;
}
}In Python, the solution employs memoization with a recursive DFS function that avoids repeating work by storing the results of subproblems.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach 3: Default Approach
function minFallingPathSum(matrix: number[][]): number {
const n = matrix.length;
const f: number[] = new Array(n).fill(0);
for (const row of matrix) {
const g = f.slice();
for (let j = 0; j < n; ++j) {
if (j > 0) {
g[j] = Math.min(g[j], f[j - 1]);
}
if (j + 1 < n) {
g[j] = Math.min(g[j], f[j + 1]);
}
g[j] += row[j];
}
f.splice(0, n, ...g);
}
return Math.min(...f);
}func minFallingPathSum(matrix [][]int) int {
n := len(matrix)
f := make([]int, n)
for _, row := range matrix {
g := make([]int, n)
copy(g, f)
for j, x := range row {
if j > 0 {
g[j] = min(g[j], f[j-1])
}
if j+1 < n {
g[j] = min(g[j], f[j+1])
}
g[j] += x
}
f = g
}
return slices.Min(f)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bottom-Up Dynamic Programming Approach | Time Complexity: O(n^2) |
| Top-Down Dynamic Programming with Memoization | Time Complexity: O(n^2) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Top-Down DP with Memoization | O(n^2) | O(n^2) | When deriving the recurrence relation or explaining the problem using recursion |
| Bottom-Up Dynamic Programming | O(n^2) | O(n^2) or O(1) in-place | Preferred for production or interviews due to iterative structure and possible space optimization |
Frequently asked questions
Is Minimum Falling Path Sum easy or hard?
Minimum Falling Path Sum is considered a medium-level problem. The challenge comes from recognizing the dynamic programming transition and handling edge columns correctly when checking diagonal neighbors.
How to solve Minimum Falling Path Sum in O(n)?
The standard solution cannot be reduced to O(n) time because every cell in the n x n matrix must be evaluated. The optimal complexity is O(n^2). However, space usage can be reduced to O(1) extra space by updating the matrix directly during the DP computation.
What is the best approach for Minimum Falling Path Sum?
The best approach is bottom-up dynamic programming. Iterate row by row and update each cell with the minimum value from the three reachable cells in the previous row. This processes the entire matrix once with O(n^2) time complexity and can be optimized to O(1) extra space by modifying the matrix in-place.
What data structure is used in Minimum Falling Path Sum?
The main data structure is a 2D matrix combined with a dynamic programming table. The DP state represents the minimum sum needed to reach each cell. Transitions use adjacent cells from the previous row.
What is the time complexity of Minimum Falling Path Sum?
The optimal dynamic programming solution runs in O(n^2) time because each of the n x n matrix cells is processed exactly once. Each computation checks at most three neighboring cells from the previous row, which is constant work.
Minimum Falling Path Sum Python or Java solution approach
Both Python and Java implementations typically use bottom-up dynamic programming. Iterate through the matrix starting from the second row and update each cell using the minimum of the three possible parent cells. The final answer is the minimum element in the last row.
Is Minimum Falling Path Sum asked at Google, Amazon, or Meta?
Minimum Falling Path Sum represents a classic grid dynamic programming pattern. Variants of this problem frequently appear in interviews at companies like Amazon, Google, and Meta where candidates must compute optimal paths in a matrix using DP transitions.