Log inSign up
mediumLeetCodeNot Started

Minimum Falling Path Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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: ``text matrix = [ [2, 1, 3], [6, 5, 4], [7, 8, 9] ] ` - **Output**: 13 - **Explanation**: Possible falling path: 1 -> 5 -> 7 (13) or 1 -> 4 -> 8` (13).

### Example 2 - Input: matrix = [[-19, 57], [-40, -5]] - Output: -59 - Explanation: Falling path: -19 -> -40 = -59.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model downward diagonal matrix traversal with boundary protection.
  • Space-optimize to a 1D row array.
  • Handle negative numbers in cell costs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Falling path on n x n matrix.
  • Transitions to (r+1, c-1), (r+1, c), (r+1, c+1).
  • Path sum minimization.

Algorithmic Decision Tree:

  • Check left and right boundary conditions.
  • Output minimum over all elements in the final row.

Connected Patterns:

Maximum Path Sum in MatrixTriangle Minimum Path SumMinimum Path Sum

1. Recursive Multi-Source DFS

Intuition

Recursively branch into all 3 downward cells from every starting column in row 0.

Algorithm

  1. Define solve(r, c).
  2. If c < 0 || c >= n, return \infty.
  3. If r == n - 1, return matrix[r][c].
  4. Return matrix[r][c] + min({solve(r+1, c-1), solve(r+1, c), solve(r+1, c+1)}).
  5. Evaluate for all c in [0, n - 1] and return minimum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r, int c, const vector<vector<int>>& mat, int n) {
9 if (c < 0 || c >= n) return 1e9;
10 if (r == n - 1) return mat[r][c];
11
12 int left = solve(r + 1, c - 1, mat, n);
13 int down = solve(r + 1, c, mat, n);
14 int right = solve(r + 1, c + 1, mat, n);
15
16 return mat[r][c] + min({left, down, right});
17 }
18public:
19 int minFallingPathSum(vector<vector<int>>& matrix) {
20 int n = matrix.size();
21 int minSum = 1e9;
22 for (int c = 0; c < n; ++c) {
23 minSum = min(minSum, solve(0, c, matrix, n));
24 }
25 return minSum;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> matrix = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
32 cout << "Min Falling Path: " << sol.minFallingPathSum(matrix) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(n * 3^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Store intermediate results for each cell in a memo table memo[n][n].

Algorithm

  1. Initialize memo[n][n] with \infty.
  2. In solve(r, c): return memo[r][c] if already computed.
  3. Evaluate min of 3 child cells.
  4. Save and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r, int c, const vector<vector<int>>& mat, int n, vector<vector<int>>& memo) {
9 if (c < 0 || c >= n) return 1e9;
10 if (r == n - 1) return mat[r][c];
11 if (memo[r][c] != 1e9) return memo[r][c];
12
13 int left = solve(r + 1, c - 1, mat, n, memo);
14 int down = solve(r + 1, c, mat, n, memo);
15 int right = solve(r + 1, c + 1, mat, n, memo);
16
17 return memo[r][c] = mat[r][c] + min({left, down, right});
18 }
19public:
20 int minFallingPathSum(vector<vector<int>>& matrix) {
21 int n = matrix.size();
22 vector<vector<int>> memo(n, vector<int>(n, 1e9));
23 int minSum = 1e9;
24 for (int c = 0; c < n; ++c) {
25 minSum = min(minSum, solve(0, c, matrix, n, memo));
26 }
27 return minSum;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<vector<int>> matrix = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
34 cout << "Min Falling Path: " << sol.minFallingPathSum(matrix) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2)

3. Space-Optimized 1D Rolling Row DP

Intuition

Maintain a 1D array of size n representing the previous row's minimum path sums.

Algorithm

  1. Initialize prev = matrix[0].
  2. For r from 1 to n - 1:
  3. Initialize curr array of size n.
  4. For c from 0 to n - 1:
  5. left = (c > 0) ? prev[c - 1] : infinity.
  6. down = prev[c].
  7. right = (c < n - 1) ? prev[c + 1] : infinity.
  8. curr[c] = matrix[r][c] + min({left, down, right}).
  9. prev = curr.
  10. Return minimum value in prev.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minFallingPathSum(vector<vector<int>>& matrix) {
10 int n = matrix.size();
11 vector<int> prev = matrix[0];
12
13 for (int r = 1; r < n; ++r) {
14 vector<int> curr(n);
15 for (int c = 0; c < n; ++c) {
16 int left = (c > 0) ? prev[c - 1] : 1e9;
17 int down = prev[c];
18 int right = (c < n - 1) ? prev[c + 1] : 1e9;
19 curr[c] = matrix[r][c] + min({left, down, right});
20 }
21 prev = move(curr);
22 }
23
24 return *min_element(prev.begin(), prev.end());
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> matrix = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
31 cout << "Min Falling Path: " << sol.minFallingPathSum(matrix) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Multi-Source DFSO(n * 3^n)O(n)Exhaustive branching over all 3 downward paths.Subproblem overlap
2.Memoized DPO(n^2)O(n^2)Cache minimum cost for each cell in memo array.Table allocation
3.Space-Optimized 1D Rolling Row DPOptimalO(n^2)O(n)Maintain only one row of prefix path minimums.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using 0 instead of infinity for out-of-bounds boundary guards.

Pitfall 2:

Forgetting to scan for the minimum among all elements in the final row.

Crucial Edge Cases to Validate:

  • 1x1 matrix: Returns matrix[0][0].
  • Negative numbers: Correctly handled by +infinity out-of-bounds guards.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the symmetry between Maximum Path Sum in Matrix and Minimum Falling Path Sum.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When initializing sentinel values for out-of-bounds columns (c < 0 or c >= n), why MUST we use +infinity instead of 0?

Back to DSA Sheet