In this guide, you will get 931. Minimum Falling Path Sum LeetCode Solution with the best time and space complexity. The solution to Minimum Falling Path Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(1)
931. Minimum Falling Path Sum LeetCode Solution in C++
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& A) {
const int n = A.size();
for (int i = 1; i < n; ++i)
for (int j = 0; j < n; ++j) {
int mn = INT_MAX;
for (int k = max(0, j - 1); k < min(n, j + 2); ++k)
mn = min(mn, A[i - 1][k]);
A[i][j] += mn;
}
return ranges::min(A[n - 1]);
}
}; /* code provided by PROGIEZ */
931. Minimum Falling Path Sum LeetCode Solution in Java
class Solution {
public int minFallingPathSum(int[][] A) {
final int n = A.length;
for (int i = 1; i < n; ++i)
for (int j = 0; j < n; ++j) {
int mn = Integer.MAX_VALUE;
for (int k = Math.max(0, j - 1); k < Math.min(n, j + 2); ++k)
mn = Math.min(mn, A[i - 1][k]);
A[i][j] += mn;
}
return Arrays.stream(A[n - 1]).min().getAsInt();
}
} // code provided by PROGIEZ
931. Minimum Falling Path Sum LeetCode Solution in Python
class Solution:
def minFallingPathSum(self, A: list[list[int]]) -> int:
n = len(A)
for i in range(1, n):
for j in range(n):
mn = math.inf
for k in range(max(0, j - 1), min(n, j + 2)):
mn = min(mn, A[i - 1][k])
A[i][j] += mn
return min(A[-1]) # code by PROGIEZ
