Minimum Falling Path Sum

111.9k
0

Given a square integer matrix with n rows and n columns, find the minimum sum of a falling path from the first row to the last row.

A falling path may start at any first-row cell. From (row, col), a valid move reaches (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1) when the destination remains inside the matrix.

Example 1

Input: matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]
Output: 13
Explanation: Falling path 1 -> 5 -> 7 has sum 13, the minimum among all valid falling paths.

Example 2

Input: matrix = [[-19, 57], [-40, -5]]
Output: -59
Explanation: Falling path -19 -> -40 has sum -59. Negative values remain valid path entries.

Recursion

Each cell offers at most three moves into the next row. Exploring all three moves covers every valid path starting from a selected cell, and the smallest returned sum gives the best continuation.

State solve(row, col) represents the minimum falling path sum starting at (row, col) and ending in the last row. The public method starts recursion from every first-row column because a falling path may begin anywhere along the top edge.

Algorithm

  • Define solve(row, col) as the minimum sum from a selected cell to the last row, so every recursive call solves the same smaller path problem.

  • Return a large cost for an invalid column because an out-of-bounds diagonal must never win a minimum comparison.

  • Return matrix[row][col] on the last row because the selected cell already completes a valid falling path.

  • Explore down-left, straight-down, and down-right moves because the movement rule permits exactly the three listed next positions.

  • Add the current cell value to the smallest child result because a valid path uses the current cell before one best continuation.

  • Start the helper from every first-row column because no fixed starting column is required by the problem.

  • Return the smallest starting result because the cheapest complete falling path may begin at any top-row cell.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the minimum sum from one selected cell.
int solve(int row, int col, vector<vector<int>>& matrix) {
int n = matrix.size();
// Invalid diagonals cannot form a falling path.
if (col < 0 || col >= n) {
return 1000000000;
}
// A last-row cell completes the falling path.
if (row == n - 1) {
return matrix[row][col];
}
// The down-left call explores the left diagonal.
int downLeft = solve(row + 1, col - 1, matrix);
// The down call preserves the current column.
int down = solve(row + 1, col, matrix);
// The down-right call explores the right diagonal.
int downRight = solve(row + 1, col + 1, matrix);
// The smallest child gives the cheapest continuation.
int bestNext = min(downLeft, min(down, downRight));
// The current value belongs to every path from the cell.
return matrix[row][col] + bestNext;
}
public:
// Returns the minimum sum among all starting columns.
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
int answer = 1000000000;
// Every top-row cell can begin a falling path.
for (int col = 0; col < n; col++) {
int pathSum = solve(0, col, matrix);
answer = min(answer, pathSum);
}
return answer;
}
};
// Driver code
int main() {
vector<vector<int>> matrix = {
{2, 1, 3},
{6, 5, 4},
{7, 8, 9}
};
Solution obj;
cout << obj.minFallingPathSum(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(N × 3N), where N is the number of rows and columns in the matrix, because each of the N starting columns can generate a recursion tree with up to three branches across N rows.

Space Complexity: O(N), because one recursive path can contain at most one active call for each matrix row.

Memoization

Different recursive branches often reach the same cell. Recalculating the full continuation from a shared cell repeats identical work and causes the exponential running time.

A two-dimensional dp array stores each completed solve(row, col) result. A later request for the same state returns the saved value, while the recursive state and three movement choices remain unchanged.

Algorithm

  • Keep the same solve(row, col) state so memoization improves the recursive approach without changing path meaning.

  • Fill a two-dimensional dp array with a large sentinel because every untouched cell must be distinguishable from a calculated sum.

  • Reject invalid columns with a large cost and finish on the last row with the cell value, preserving the original base cases.

  • Return dp[row][col] after a cache hit because the cheapest continuation from a fixed cell never changes.

  • Explore all three valid movement directions for an uncached state because every legal continuation must remain available.

  • Store the current value plus the smallest child result in dp[row][col] so later branches avoid repeated exploration.

  • Evaluate every first-row column and return the smallest result because any top-row cell may start the optimal path.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns a saved or newly calculated minimum sum.
int solve(int row, int col, vector<vector<int>>& matrix,
vector<vector<int>>& dp) {
int n = matrix.size();
// Invalid diagonals cannot form a falling path.
if (col < 0 || col >= n) {
return 1000000000;
}
// A last-row cell completes the falling path.
if (row == n - 1) {
return matrix[row][col];
}
// A saved state avoids an identical recursive search.
if (dp[row][col] != 1000000000) {
return dp[row][col];
}
// The down-left call explores the left diagonal.
int downLeft = solve(row + 1, col - 1, matrix, dp);
// The down call preserves the current column.
int down = solve(row + 1, col, matrix, dp);
// The down-right call explores the right diagonal.
int downRight = solve(row + 1, col + 1, matrix, dp);
// The smallest child gives the cheapest continuation.
int bestNext = min(downLeft, min(down, downRight));
// The completed state is saved for later branches.
dp[row][col] = matrix[row][col] + bestNext;
return dp[row][col];
}
public:
// Returns the minimum sum among all starting columns.
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
// The sentinel marks every uncalculated state.
vector<vector<int>> dp(
n, vector<int>(n, 1000000000)
);
int answer = 1000000000;
// Every top-row cell can begin a falling path.
for (int col = 0; col < n; col++) {
int pathSum = solve(0, col, matrix, dp);
answer = min(answer, pathSum);
}
return answer;
}
};
// Driver code
int main() {
vector<vector<int>> matrix = {
{2, 1, 3},
{6, 5, 4},
{7, 8, 9}
};
Solution obj;
cout << obj.minFallingPathSum(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of rows and columns in the matrix, because at most N × N states are computed once and each state checks three constant-time transitions.

Space Complexity: O(N2), because the dp table stores N × N results, while the recursion stack adds only O(N) space.

Tabulation

Memoization waits for recursive calls before calculating a state. Tabulation removes the call stack by filling the same states in an order matching the dependencies.

The last matrix row forms the base row of dp. Processing upward then calculates each dp[row][col] from down-left, down, and down-right entries in dp[row + 1], so every required child value is already available.

Algorithm

  • Create an n by n array named dp because every recursive state needs one iterative storage position.

  • Copy the last matrix row into the last dp row because each last-row cell already completes a falling path.

  • Process rows from n - 2 upward to 0 so all three child states in the next row are available before a parent state.

  • Keep a large cost for any diagonal outside the matrix because an invalid move must not become the minimum choice.

  • Read down-left, down, and down-right values from dp[row + 1] to preserve the recursive movement choices exactly.

  • Store the current matrix value plus the smallest child value in dp[row][col] because each table entry represents the same minimum-sum state.

  • Return the minimum value in dp[0] because every first-row column remains a valid starting position.

Dry Run

Minimum Falling Path sum Tabulation

Minimum Falling Path sum Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum falling path sum with a table.
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
// The table stores one result for every matrix cell.
vector<vector<int>> dp(n, vector<int>(n, 0));
// The last row supplies every recursive base state.
for (int col = 0; col < n; col++) {
dp[n - 1][col] = matrix[n - 1][col];
}
// Upward order keeps the next row ready for use.
for (int row = n - 2; row >= 0; row--) {
for (int col = 0; col < n; col++) {
int downLeft = 1000000000;
int down = dp[row + 1][col];
int downRight = 1000000000;
// A left diagonal exists beyond the first column.
if (col > 0) {
downLeft = dp[row + 1][col - 1];
}
// A right diagonal exists before the last column.
if (col + 1 < n) {
downRight = dp[row + 1][col + 1];
}
// The smallest child preserves the recurrence.
int bestNext = min(
downLeft, min(down, downRight)
);
// The cell value extends the best child path.
dp[row][col] = matrix[row][col] + bestNext;
}
}
// Any first-row column may start the optimal path.
return *min_element(dp[0].begin(), dp[0].end());
}
};
// Driver code
int main() {
vector<vector<int>> matrix = {
{2, 1, 3},
{6, 5, 4},
{7, 8, 9}
};
Solution obj;
cout << obj.minFallingPathSum(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of rows and columns in the matrix, because every matrix cell is processed once with constant transition work.

Space Complexity: O(N2), because the dp table stores one minimum path sum for every matrix cell and no recursion stack is used.

Space Optimization

Every tabulation state reads values only from the next row. Rows below the next row never appear in a later calculation, so the full two-dimensional table stores more history than the recurrence needs.

Array nextRow keeps the already calculated child states, while array current receives one parent row. After every column in current is complete, current replaces nextRow; the delayed shift protects all child values from early overwrites.

Algorithm

  • Copy the last matrix row into nextRow because the final row contains all base-state values required by the row above.

  • Process remaining rows from bottom to top so nextRow always represents the three possible child positions.

  • Create a fresh current array for each row because every new parent state must read the unchanged child row.

  • Use a large cost for a missing left or right diagonal because an out-of-bounds move cannot form a valid path.

  • Calculate each current[col] from the matrix value and the smallest valid entry in nextRow, preserving the original recurrence.

  • Shift current into nextRow only after the full row is calculated so later columns never read partially updated child values.

  • Return the minimum value in the final nextRow because the last shift stores all possible first-row starting sums.

Dry Run

Minimum Falling Path sum Space optimization

Minimum Falling Path sum Space optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum sum with two rolling rows.
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
// The final row supplies every base-state value.
vector<int> nextRow = matrix[n - 1];
// Upward order keeps one complete child row available.
for (int row = n - 2; row >= 0; row--) {
vector<int> current(n, 0);
for (int col = 0; col < n; col++) {
int downLeft = 1000000000;
int down = nextRow[col];
int downRight = 1000000000;
// A left diagonal exists beyond the first column.
if (col > 0) {
downLeft = nextRow[col - 1];
}
// A right diagonal exists before the last column.
if (col + 1 < n) {
downRight = nextRow[col + 1];
}
// Current uses only the unchanged child row.
int bestNext = min(
downLeft, min(down, downRight)
);
current[col] = matrix[row][col] + bestNext;
}
// The shift occurs after every current state is ready.
nextRow = current;
}
// The final rolling row stores every starting sum.
return *min_element(nextRow.begin(), nextRow.end());
}
};
// Driver code
int main() {
vector<vector<int>> matrix = {
{2, 1, 3},
{6, 5, 4},
{7, 8, 9}
};
Solution obj;
cout << obj.minFallingPathSum(matrix);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of rows and columns in the matrix, because every matrix cell is processed once using at most three constant-time transitions.

Space Complexity: O(N), because nextRow and current each store N values, while all older rows are discarded.

Interview follow-up Questions

Yes. Any first-row cell may start a path, and any last-row cell may end a path. Only movement between consecutive rows is restricted.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Input: nums = [1, 16, 7, 8, 4] Output: [1, 4, 8, 16] Explanation: Every pair inside [1, 4, 8, 16] satisfies the divisibility rule. The value 7 cannot join the chain because no other chain value div...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals targe...

55.1k
Comments0