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] <= 100Using 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.
In the C solution, we iterate from the second-last row to the first row, and for each element, we compute the minimum sum from possible paths below. We update the original matrix with these minimum values and finally compute the minimum value in the first row.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) because each element is visited once.
Space Complexity: O(1) since the computations are done in place.
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.
In the C solution, a recursive function with memoization is used to compute the minimum falling path sum starting from every element in the first row. The memo table avoids recalculation of already known results.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to memoization reducing redundant calculations.
Space Complexity: O(n^2) due to the memoization table.
| Approach | Complexity |
|---|---|
| Bottom-Up Dynamic Programming Approach | Time Complexity: O(n^2) because each element is visited once. |
| Top-Down Dynamic Programming with Memoization | Time Complexity: O(n^2) due to memoization reducing redundant calculations. |
Google Medium Dynamic Programming Problem - Leetcode 64 - Minimum Path Sum • Greg Hogg • 420,074 views views
Watch 9 more video solutions →Practice Minimum Falling Path Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor