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] <= 100The key idea in Minimum Falling Path Sum is to compute the minimum cost of reaching each cell while moving from the top row to the bottom row. From any cell (i, j), the next step can go directly down, diagonally left-down, or diagonally right-down. This structure naturally leads to a dynamic programming approach.
Instead of exploring every possible path, we store the minimum sum needed to reach each cell. For each position, we update its value using the minimum of the three possible previous positions from the row above. This avoids recomputation and builds the answer row by row.
The final answer is the minimum value in the last row after processing all transitions. The DP can be implemented either with a separate matrix or optimized to reuse the original matrix for O(1) extra space. The overall time complexity is O(n²) since each cell is processed once, and the space complexity ranges from O(n²) to O(1) depending on optimization.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with DP Matrix | O(n^2) | O(n^2) |
| Optimized In-place Dynamic Programming | O(n^2) | O(1) |
Greg Hogg
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.
Time Complexity: O(n^2) because each element is visited once.
Space Complexity: O(1) since the computations are done in place.
1var minFallingPathSum = function(matrix) {
2 const n = matrix.length;
3 for (let i = n - 2; i >= 0;JavaScript solution accumulates the minimum path sums by modifying the matrix from the bottom row up and finally finds the minimum sum in the top row.
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.
Time Complexity: O(n^2) due to memoization reducing redundant calculations.
Space Complexity: O(n^2) due to the memoization table.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Dynamic programming problems similar to Minimum Falling Path Sum frequently appear in technical interviews at companies like FAANG. They test a candidate's ability to identify overlapping subproblems and optimize solutions using DP.
A 2D array or matrix is the primary data structure used. It stores intermediate minimum path sums for each cell, allowing efficient updates based on neighboring values from the previous row.
The optimal approach uses dynamic programming. For each cell, compute the minimum path sum by considering the three possible cells from the previous row. This avoids exploring all paths and reduces the complexity to O(n^2).
Yes, the problem can be optimized by updating the input matrix in place or by keeping only the previous row. This reduces the extra space requirement from O(n^2) to O(1) or O(n).
JavaScript solution uses recursive function with memoization to compute minimum falling path sum starting from each element in the first row, caching results for efficiency.