Minimum Path Sum
Find the cheapest path from the top-left to the bottom-right of a grid when you can only move right or down. A first taste of 2D dynamic programming on a grid. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an m x n grid of non-negative integers. Start in the top-left cell and travel to the bottom-right cell, moving only right or down one cell at a time.
The cost of a path is the sum of every cell it visits, including the first and last cells. Return the smallest possible cost.
Example 1
- Input
- grid = [[2, 9, 1], [3, 4, 2], [8, 1, 1]]
- Output
- 11
Go down, right, down, right: 2 → 3 → 4 → 1 → 1 = 11.
Example 2
- Input
- grid = [[4, 1, 5]]
- Output
- 10
With one row, the only path goes straight across.
Example 3
- Input
- grid = [[0, 7], [0, 0]]
- Output
- 0
Going down first and then right avoids the 7.
Constraints
- 1 ≤ m, n ≤ 200
- 0 ≤ grid[i][j] ≤ 200
- Moves are only to the right or down.
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Minimum Path Sum in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Minimum Path Sum
Pattern: 2D grid dynamic programming
Because you can only move right or down, the last step into any cell (i, j) came either from the cell above or from the cell to the left. So the cheapest way to reach (i, j) is its own value plus the cheaper of those two.
That gives the recurrence best[i][j] = grid[i][j] + min(best[i-1][j], best[i][j-1]), with the first row and first column only having one way in. Fill the table row by row and the bottom-right entry is the answer.
Notice that row i only depends on row i - 1 and on the cell to its left, so a single 1D array of length n is enough.
Approach 1: Try every path recursively
From each cell, recurse right and down and return the smaller total. There are C(m + n - 2, m - 1) paths, which explodes quickly; a 20 x 20 grid already has over 35 billion.
Time O(2^(m + n)) · Space O(m + n) recursion depth
Approach 2: Memoized recursion or full 2D table
Cache the best cost to reach each cell, or fill an m x n table with the recurrence. Each cell is computed once from two neighbors.
Time O(m · n) · Space O(m · n)
Approach 3: Rolling 1D array
Keep dp of length n, where dp[j] is the best cost to reach column j in the current row.
- For the first row,
dp[j] = dp[j-1] + grid[0][j]. - For each later row,
dp[0] += grid[i][0], then forj ≥ 1:dp[j] = grid[i][j] + min(dp[j], dp[j-1]). Heredp[j]still holds the value from the row above anddp[j-1]was just updated for this row. - Return
dp[n-1].
Time O(m · n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Try every path recursively | O(2^(m + n)) | O(m + n) recursion depth |
| Memoized recursion or full 2D table | O(m · n) | O(m · n) |
| Rolling 1D array | O(m · n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Minimum Path Sum solution in Python
def min_path_sum(grid: list[list[int]]) -> int:
n = len(grid[0])
dp = [0] * n
for i, row in enumerate(grid):
for j, value in enumerate(row):
if i == 0 and j == 0:
dp[j] = value
elif i == 0:
dp[j] = dp[j - 1] + value
elif j == 0:
dp[j] += value
else:
dp[j] = value + min(dp[j], dp[j - 1])
return dp[-1]Minimum Path Sum solution in JavaScript
function minPathSum(grid) {
const n = grid[0].length;
const dp = new Array(n).fill(0);
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < n; j++) {
const value = grid[i][j];
if (i === 0 && j === 0) dp[j] = value;
else if (i === 0) dp[j] = dp[j - 1] + value;
else if (j === 0) dp[j] += value;
else dp[j] = value + Math.min(dp[j], dp[j - 1]);
}
}
return dp[n - 1];
}Common mistakes
- Treating the first row and first column like interior cells and reading out of bounds (or taking min with an uninitialized 0, which undercounts).
- Forgetting to include the starting cell's value in the total.
- Trying a greedy "always step to the cheaper neighbor", which can walk into an expensive region later.
- Using Dijkstra or BFS. It works since weights are non-negative, but it is slower and more complicated than the DP the movement rule allows.
What interviewers look for
Explain where the recurrence comes from: "the only ways into a cell are from above or from the left." That sentence is the whole solution, and interviewers want to hear it before code. Then mention the base cases for the first row and column explicitly.
Offer the space optimization after you have the 2D version working, and say why it is safe: each row only reads the row above and the cell to its left.
Follow-up questions
How would you return the actual path, not just its cost?
Keep the full 2D table. Starting at the bottom-right, step to whichever of the cell above or to the left has the smaller stored cost, until you reach the top-left. Reverse the collected cells.
What if you could move in all four directions?
The grid now has cycles, so the simple DP order no longer works. Since costs are non-negative, run Dijkstra's algorithm from the top-left with a min-heap, which costs O(m · n · log(m · n)).
What if some cells are blocked?
Treat a blocked cell as having infinite cost so it is never chosen, and return -1 (or similar) if the bottom-right stays infinite. The recurrence and its O(m · n) cost are otherwise unchanged.
Companies that ask Minimum Path Sum
Minimum Path Sum is tagged by 104 companies in our interview dataset. The score shows how often it comes up at each company.
- Loom100%
- D2l100%
- Klaviyo100%
- Slack100%
- Zimmer Biomet100%
- Synechron100%
- Lime100%
- Dialpad100%
- American Airlines100%
- Texas Instruments100%
- Cdk Global98%
- Duckduckgo98%
- Just Eat97%
- Revature96%
- Arrow Electronics96%
- Nebius94%
- Rackspace94%
- Apptio92%
- Micro Focus92%
- Culture Amp91%
- 1mg89%
- Chamberlain Group88%
- Slalom Build83%
- Corelight83%
and 80 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required