Minimum Falling Path Sum
PhonePeThe problem
Given a 2d array called **matrix **consisting of **integer **values. Return the **minimum **path sum that can be obtained by **starting **at **any **cell in the **first **row and **ending **at **any **cell in the **last **row.
Movement is allowed only to the bottom, bottom-right, or **bottom-left **cell of the current cell.
Input: matrix = [[1, 2, 10, 4], [100, 3, 2, 1], [1, 1, 20, 2], [1, 2, 2, 1]] Output: 6 Explanation: One optimal route can be:- Start at 1st cell of 1st row -> bottom-right -> bottom -> bottom-left.
Input: matrix = [[1, 4, 3, 1], [2, 3, -1, -1], [1, 1, -1, 8]] Output: -1 Explanation: One optimal route can be:- Start at 4th cell of 1st row -> bottom-left -> bottom.
Input: matrix = [[4, 3, 4], [4, 5, 1], [4, 6, 2], [4, 1, 4]]
- m == number of rows in matrix
- n == number of columns in matrix
- 1 <= n, m <= 100
- -1000 <= matrix[i][j] <= 1000
- The answer will not exceed 109
cpp
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
}
};java
class Solution {
public int minFallingPathSum(int[][] matrix) {
}
}python
class Solution:
def minFallingPathSum(self, matrix):javascript
class Solution {
minFallingPathSum(matrix) {
}
}csharp
public class Solution {
public int MinFallingPathSum(int[][] matrix) {
}
}go
func minFallingPathSum(matrix [][]int) int {
}Stuck? Show a way to structure it+
- 01Let dp[c] represent the best sum ending at column c in the prior row.
- 02For each cell, take its value plus the minimum of up-left, up, and up-right.
- 03Treat unavailable diagonal parents as infinity.
- 04Return the minimum value in the final row.
Reference answer
Then expect these follow-ups
How would you return the path itself?
Tests: parent pointers
What changes when moves are only down and down-right?
Tests: recurrence design
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question