DSA
Minimum Falling Path Sum
Covers: Recursive, Memoized. Optimal — Time O(m*n), Space O(m*n).
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).
Practice Link
Recursive#
From each starting column in the first row, we follow the falling path by choosing the minimum of the three valid moves (diagonally left, straight down, diagonally right) at each step. The recursion bottoms out at the last row, where we return the cell value directly. Because multiple paths can reach the same (i, j) cell, sub-problems overlap and are recomputed many times without caching.
class Solution {
public:
int findMinFallingPath(vector<vector<int>>& matrix, int i, int j)
{
if(i==matrix.size()-1)
return matrix[i][j];
int left=INT_MAX, bottom, right=INT_MAX;
if(j>0)
left = findMinFallingPath(matrix, i+1, j-1);
bottom = findMinFallingPath(matrix, i+1, j);
if(j<matrix.size()-1)
right = findMinFallingPath(matrix, i+1, j+1);
return matrix[i][j] + min({left, bottom, right});
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int minSum = INT_MAX;
for(int col=0;col<n;col++)
{
minSum = min(minSum, findMinFallingPath(matrix, 0, col));
}
return minSum;
}
};
TLE - overlapping cases
Memoized#
Cache the minimum falling-path cost from each cell (i, j) to the last row. Each of the m × n cells is computed exactly once, reducing time to O(m*n). The sentinel value -10000 is used instead of -1 because cell sums can be negative, so -1 would be a valid cached answer and would cause incorrect cache hits.
Note: here the memo vector had to be initialized with -10000, since constraints say -100 <= matrix[i][j] <= 100, which if initialized to -1 would give TLE as -1 could be a valid answer.
class Solution {
public:
int findMinFallingPath(vector<vector<int>>& matrix, int i, int j, vector<vector<int>> &memo)
{
if(i==matrix.size()-1)
return matrix[i][j];
if(memo[i][j] != -10000)
return memo[i][j];
int left=INT_MAX, bottom, right=INT_MAX;
if(j>0)
left = findMinFallingPath(matrix, i+1, j-1, memo);
bottom = findMinFallingPath(matrix, i+1, j, memo);
if(j<matrix.size()-1)
right = findMinFallingPath(matrix, i+1, j+1, memo);
return memo[i][j] = matrix[i][j] + min({left, bottom, right});
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> memo(m, vector<int>(n, -10000));
int minSum = INT_MAX;
for(int col=0;col<n;col++)
{
minSum = min(minSum, findMinFallingPath(matrix, 0, col, memo));
}
return minSum;
}
};
Time Complexity: O(m*n)
Space Complexity: O(n)
Tabulation#
Build the minimum-cost table top-down (first row = matrix values; each subsequent row adds the current cell's value to the minimum of its three predecessors in the row above). The last row of dp holds the minimum path cost ending at each column; the answer is their minimum. This eliminates the recursion stack and runs in O(mn) time and O(mn) space.
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int j=0;j<n;j++){
dp[0][j] = matrix[0][j];
}
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
int up = dp[i-1][j];
int left = 1e9;
if(j-1 >=0)
left = dp[i-1][j-1];
int right = 1e9;
if(j+1 < n)
right = dp[i-1][j+1];
dp[i][j] = matrix[i][j] + min(up, min(left, right));
}
}
return *min_element(dp[m-1].begin(), dp[m-1].end());
}
};
Time Complexity: O(m*n)
Space Complexity: O(m*n) + O(m) = O(m*n)