Minimum Path Sum
Problem
m × n grid of non-negative integers. Travel
from the top-left cell to the bottom-right cell moving only right or
down, and return the smallest possible sum of the values on the cells you visit
(both ends included).[[1,3,1],[1,5,1],[4,2,1]]Output7 (1→3→1→1→1)[[1,2,3],[4,5,6]]Output121 ≤ m, n ≤ 200 · 0 ≤ grid[i][j] ≤ 200
Try it yourself
class Solution {
public int minPathSum(int[][] grid) {
}
}
(i, j) must come from the cheaper of
its top or left neighbour, so
best(i,j) = grid[i][j] + min(best(i-1,j), best(i,j-1)). Fill row by row.Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.
Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.
Open the Grid DP guide →Approaches
Brute ForceRecursion (Min of Top / Left)
O(2m+n)Space O(m + n)minSum(i, j) = cheapest path from (0,0) to
(i,j). On the first row or column there is only one way in;
elsewhere take the cheaper of the top and left sub-answers. Overlapping
sub-problems are recomputed again and again.
public int minPathSum(int[][] grid) { return minSum(grid, grid.length - 1, grid[0].length - 1); } private int minSum(int[][] grid, int i, int j) { if (i == 0 && j == 0) return grid[0][0]; if (i == 0) return grid[i][j] + minSum(grid, i, j - 1); // only from left if (j == 0) return grid[i][j] + minSum(grid, i - 1, j); // only from top return grid[i][j] + Math.min(minSum(grid, i - 1, j), minSum(grid, i, j - 1)); }
Captures the recurrence, but exponential — useless for 200×200.
BetterBottom-Up 2D DP Table
O(m · n)Space O(m · n)Compute the same recurrence iteratively in a table dp, row
by row, so every cell’s top and left values are ready when needed. The
first row and column are running prefix sums.
public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) dp[i][j] = grid[0][0]; else if (i == 0) dp[i][j] = grid[i][j] + dp[i][j - 1]; else if (j == 0) dp[i][j] = grid[i][j] + dp[i - 1][j]; else dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; }
Each cell computed once; the extra table is the only cost.
OptimalIn-Place DP on the Grid
O(m · n)Space O(1)Once grid[i][j] has been read it is never needed again, so
overwrite it with its best path sum. The grid itself becomes the DP table and no
extra memory is used (the input is modified).
public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) continue; if (i == 0) grid[i][j] += grid[i][j - 1]; else if (j == 0) grid[i][j] += grid[i - 1][j]; else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; }
Dry run[[1,3,1],[1,5,1],[4,2,1]] (row after update)
- row 0145prefix sums
- row 1276e.g. 1+min(5,7)=6
- row 26871+min(6,8)=7 ✔
Optimal time and O(1) extra space — mention that it mutates the input.
dp[n] instead:
dp[j] = g[i][j] + min(dp[j], dp[j-1]) — O(n) space.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursion (Min of Top / Left) | O(2m+n) | O(m + n) |
| Better | Bottom-Up 2D DP Table | O(m · n) | O(m · n) |
| Optimal | In-Place DP on the Grid | O(m · n) | O(1) |
- Treating the first row/column like inner cells — out-of-bounds or wrong mins.
- Using
Integer.MAX_VALUEas a sentinel and adding to it — overflow. - Mutating the grid without saying so — callers may reuse it.
- Explain why greedy (cheapest next step) fails: a cheap step can lead to an expensive area.
- Ask whether modifying the input is allowed before choosing in-place.
- Same template as Unique Paths: replace
+withmin+ cell cost.