Minimum Path Sum

55.3k
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 in the matrix, because each of the N starting columns can generate a recursion tree with up to three branches at each row.

Space Complexity: O(N), where N is the number of rows in the matrix, because a recursive path can contain at most one call for each matrix row.

Memoization

Different recursive paths can reach the same (row, col) cell. Without memoization, the minimum path sum from that cell is recalculated repeatedly, causing the same subproblems to be solved many times.

A two-dimensional dp array stores the minimum path sum starting from each cell. When a state has already been calculated, its saved result is returned immediately. The recursive state and the three possible downward movements remain unchanged.

Algorithm

  • Keep the same solve(row, col) state because it represents the minimum path sum starting from the current cell.

  • Fill the dp array with -1 so an uncalculated state can be distinguished from a valid path sum.

  • Return a very large cost when col goes outside the matrix because an invalid path must never be selected.

  • Return grid[row][col] when row reaches the last row because the current cell becomes the final cell of the path.

  • Return dp[row][col] when the state is already calculated because the same cell always has the same minimum continuation.

  • Explore the three downward moves (row + 1, col - 1), (row + 1, col), and (row + 1, col + 1) because these are the only valid next positions.

  • Add the current cell value to the minimum of the three child results because the path cost includes the current cell.

  • Store the result in dp[row][col] so future paths reaching the same cell can reuse it.

  • Try every column in the first row as a starting point because the path can begin from any top-row cell.

  • Return the minimum result among all first-row starting positions because the goal is to find the globally minimum falling path sum.

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(N²), where N is the number of rows/columns in the square matrix, because at most N × N states are calculated once, and each state checks three constant-time transitions.

Space Complexity: O(N² + N), where N is the number of rows/columns in the square matrix, because the dp array stores N × N results and the recursion stack contains at most O(N) calls.

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

Diagram 1
1 / 2

Diagram 1

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(N²), where N is the number of rows/columns in the square matrix, because two nested loops process every matrix cell, and each cell performs a constant-time transition.

Space Complexity: O(N²), where N is the number of rows/columns in the square matrix, because the dp array stores the minimum 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

Diagram 1
1 / 2

Diagram 1

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(N²), because there are O(N²) matrix cells and each cell performs a constant-time transition using at most three values.

Space Complexity: O(N), because nextRow and current each store O(N) values, while 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

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or secon...

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 be held at a t...

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 target ; otherwise,...

55.1k
Comments0