DSA
Minimum Path Sum
4 approaches incl. Recursive, Memoized Version, Tabulation: Space Optimized, and more. Optimal — Time O(m*n), Space O(m*n).
Practice Link
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Intuition#
The only way to arrive at cell (m, n) is from directly above (m-1, n) or directly to the left (m, n-1) — same set of predecessors as Unique Paths. The difference is what we're optimizing: instead of counting the ways to reach a cell, we want the cheapest path, so the combination step is min instead of +:
cost(m, n) = grid[m][n] + min(cost(m-1, n), cost(m, n-1))
with base case cost(0, 0) = grid[0][0], and any out-of-bounds predecessor treated as INT_MAX (an unusable path, so min never picks it).
- Recursive: direct translation of the recurrence; the same cell gets recomputed by every path that passes through it — exponential blowup.
- Memoized: caches minPathSumUtil(m, n) the first time each state is solved — O(m×n).
- Tabulation: fills the dp grid bottom-up. The first row and first column are seeded separately (dp[i][0] = grid[i][0] + dp[i-1][0], and similarly along the top row) since those cells only have one possible predecessor each, not two — you can't take a min over a direction that's off the grid.
- Tabulation, space optimized: since row i only ever depends on row i-1 (prev) and the values already computed earlier in row i itself (curr[j-1]), the full m x n grid collapses to two 1D rows.
- BFS Approach: reframes the grid as a DAG and does repeated relaxation — whenever a cheaper cost to a neighboring cell is found, push it back onto the queue. This works correctly here (unlike a general weighted graph, where plain BFS isn't suffficient) because every path from (0,0) to any cell (x,y) takes exactly x+y moves, so the grid is naturally layered by Manhattan distance. The queue processes strictly layer by layer, meaning every predecessor of a cell has been fully relaxed before that cell is dequeued for the first time — effectively a topological-order relaxation, just without needing to compute the topological order explicitly.
Sample#
Output: 7
Recursive Solution#
class Solution {
public:
int minPathSumUtil(vector<vector<int>>& grid, int m, int n)
{
if(m==0 && n==0)
return grid[0][0];
if(m<0 || n<0)
return INT_MAX;
return grid[m][n] + min(minPathSumUtil(grid, m-1,n), minPathSumUtil(grid, m, n-1));
}
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n= grid[0].size();
return minPathSumUtil(grid, m-1,n-1);
}
};
Time Complexity: O(2^n)
Space Compelexity: O(n)
Memoized Version#
class Solution {
public:
int minPathSumUtil(vector<vector<int>>& grid, int m, int n, vector<vector<int>> &memo)
{
if(m==0 && n==0)
return grid[0][0];
if(m<0 || n<0)
return INT_MAX;
if(memo[m][n] != -1)
return memo[m][n];
return memo[m][n] = grid[m][n] + min(minPathSumUtil(grid, m-1,n, memo), minPathSumUtil(grid, m, n-1, memo));
}
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n= grid[0].size();
vector<vector<int>> memo(m, vector<int>(n, -1));
return minPathSumUtil(grid, m-1,n-1, memo);
}
};
Time Complexity: O(m*n)
Space Complexity: O(m*n) + O(n)
Tabulation#
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n= grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = grid[0][0];
for(int i=1;i<m;i++)
dp[i][0] = grid[i][0] + dp[i-1][0];
for(int j=1;j<n;j++)
dp[0][j] = grid[0][j] + dp[0][j-1];
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
};
Time Complexity: O(m*n)
Space Complexity: O(m*n)
Tabulation: Space Optimized#
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> prev(n), curr(n);
prev[0] = grid[0][0];
//first row
for(int j=1;j<n;j++){
prev[j] = prev[j-1] + grid[0][j];
}
for(int i=1;i<m;i++){
fill(curr.begin(), curr.end(), 0);
for(int j=0;j<n;j++){
if(j==0){
curr[j] = prev[j] + grid[i][j];
}else{
curr[j] = grid[i][j] + min(prev[j], curr[j-1]);
}
}
prev = curr;
}
return prev[n-1];
}
};
Time Complexity: O(m*n)
Space Complexity: O(n)
BFS Approach#
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> path(m, vector<int>(n, INT_MAX));
path[0][0] = grid[0][0];
queue<pair<int,int>> q;
q.push({0,0});
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
if(x==m-1 && y == n-1)
return path[x][y];
if(x+1 < m)
{
if(path[x+1][y] > path[x][y] + grid[x+1][y])
{
q.push({x+1,y});
path[x+1][y] = path[x][y] + grid[x+1][y];
}
}
if(y+1 < n)
{
if(path[x][y+1] > path[x][y] + grid[x][y+1])
{
q.push({x,y+1});
path[x][y+1] = path[x][y] + grid[x][y+1];
}
}
}
return 0;
}
};
Time Complexity: O(m*n) — each cell has only 2 predecessors (top, left), so it can be relaxed and re-pushed onto the queue at most twice; total work is bounded by a constant factor of the number of cells.
Space Complexity: O(m*n) for the path grid, plus O(m*n) worst case for the queue (since a cell can be enqueued more than once).