Code Implementation

class Solution:
    def minFallingPathSum(self, matrix):
        n = len(matrix)
        # Start from the second last row and move upwards
        for i in range(n - 2, -1, -1):
            for j in range(n):
                # For each cell, add the minimum of the three possible cells below
                best_below = matrix[i+1][j]
                if j > 0:
                    best_below = min(best_below, matrix[i+1][j-1])
                if j < n-1:
                    best_below = min(best_below, matrix[i+1][j+1])
                matrix[i][j] += best_below
        return min(matrix[0])
      

class Solution {
public:
    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 best_below = matrix[i+1][j];
                if (j > 0)
                    best_below = min(best_below, matrix[i+1][j-1]);
                if (j < n-1)
                    best_below = min(best_below, matrix[i+1][j+1]);
                matrix[i][j] += best_below;
            }
        }
        return *min_element(matrix[0].begin(), matrix[0].end());
    }
};
      

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 bestBelow = matrix[i+1][j];
                if (j > 0)
                    bestBelow = Math.min(bestBelow, matrix[i+1][j-1]);
                if (j < n-1)
                    bestBelow = Math.min(bestBelow, matrix[i+1][j+1]);
                matrix[i][j] += bestBelow;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int num : matrix[0]) {
            min = Math.min(min, num);
        }
        return min;
    }
}
      

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    for (let i = n - 2; i >= 0; --i) {
        for (let j = 0; j < n; ++j) {
            let bestBelow = matrix[i+1][j];
            if (j > 0)
                bestBelow = Math.min(bestBelow, matrix[i+1][j-1]);
            if (j < n-1)
                bestBelow = Math.min(bestBelow, matrix[i+1][j+1]);
            matrix[i][j] += bestBelow;
        }
    }
    return Math.min(...matrix[0]);
};
      

Problem Description

You are given a square 2D array matrix of size n x n consisting of integers. A falling path starts at any element in the first row and chooses one element from each row, moving down to the next row each time. When moving from row i to row i+1, you may only move to the element directly below, or diagonally left/right (i.e., columns j-1, j, or j+1).

Your task is to find the minimum possible sum of a falling path through matrix.

• Each move must go to the next row.
• At each step, you can only move to one of the three adjacent cells in the next row.
• You can start at any element in the first row.
• There is always at least one valid path.
• You cannot skip rows or move outside the matrix.

Thought Process

At first glance, the problem seems to require checking all possible paths from the top row to the bottom, summing their values, and finding the minimum. For a matrix of size n, there could be up to 3^n possible paths (since at each step, you have up to 3 choices).

However, this brute-force approach is not efficient for larger matrices. Instead, we can observe that the minimum path sum to a cell in a given row only depends on the minimum path sums to the three possible cells above it. This suggests a dynamic programming approach, where we build up the solution row by row, reusing previously computed results.

By thinking in terms of "what is the minimum cost to reach this cell?", we can optimize away redundant calculations and avoid recomputing the same subproblems.

Solution Approach

• Dynamic Programming Table: We use the original matrix as our DP table. Each cell matrix[i][j] will represent the minimum falling path sum to reach cell (i, j) from the top row.
• Bottom-Up Calculation: We process the matrix from the second-last row upwards to the first row. For each cell, we add the minimum value among the three possible cells directly below it in the next row (same column, left-diagonal, right-diagonal).
• Edge Handling: For cells at the leftmost or rightmost columns, we only consider valid indices to avoid accessing outside the matrix.
• Result: After updating all rows, the answer is the minimum value in the first row, since any of those cells could have been the start of a minimum falling path.

This approach ensures we only compute each subproblem once, and each cell's value accumulates the minimum path sum up to that point. The solution is both efficient and easy to implement.

Example Walkthrough

Consider the following matrix:

    [2, 1, 3]
    [6, 5, 4]
    [7, 8, 9]
  

1. Start from the second-last row (i = 1):
   • For matrix[1][0]: possible next cells are matrix[2][0] and matrix[2][1] (values 7 and 8). Minimum is 7. Update: 6 + 7 = 13.
   • For matrix[1][1]: possible next cells are matrix[2][0], matrix[2][1], matrix[2][2] (values 7, 8, 9). Minimum is 7. Update: 5 + 7 = 12.
   • For matrix[1][2]: possible next cells are matrix[2][1], matrix[2][2] (values 8, 9). Minimum is 8. Update: 4 + 8 = 12.

   Now the matrix is:

           [2, 1, 3]
           [13, 12, 12]
           [7, 8, 9]
         

2. Move to the first row (i = 0):
   • For matrix[0][0]: next cells are matrix[1][0], matrix[1][1] (13, 12). Minimum is 12. Update: 2 + 12 = 14.
   • For matrix[0][1]: next cells are matrix[1][0], matrix[1][1], matrix[1][2] (13, 12, 12). Minimum is 12. Update: 1 + 12 = 13.
   • For matrix[0][2]: next cells are matrix[1][1], matrix[1][2] (12, 12). Minimum is 12. Update: 3 + 12 = 15.

   Now the matrix is:

           [14, 13, 15]
           [13, 12, 12]
           [7, 8, 9]
         

3. The answer is the minimum in the first row: 13.

Time and Space Complexity

• Brute-Force: For each cell in the first row, recursively try all possible falling paths. At each step, up to 3 choices, for n rows: O(3^n). This quickly becomes infeasible for large n.
• Optimized DP Approach:
  • We process each cell exactly once. There are n x n cells, and each update takes O(1) time.
  • Time Complexity: O(n^2)
  • Space Complexity: O(1) extra space if we modify the input matrix in-place, or O(n^2) if we use a separate DP table.

Summary

The Minimum Falling Path Sum problem is a classic example of dynamic programming applied to grid traversal. By recognizing overlapping subproblems and using a bottom-up approach, we avoid redundant work and achieve a much faster solution than brute-force. The key insight is that the minimum path sum to each cell depends only on the minimum path sums to the three possible cells above it, which allows for an elegant and efficient solution.