Coding · Dynamic programming
Minimum Path Sum
- Reported once
- Medium
- SDE-2
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A grid of non-negative integers is given, and you travel from the top-left cell to the bottom-right cell, moving only right or down and adding the value of every cell you stand on, including the first and the last. Return the smallest possible total. For [[2,1,3],[4,8,1],[7,2,1]] the answer is 8, using the path 2, 1, 3, 1, 1. The grid can be up to 200 by 200.
Restated in our own words, not a quote from Dream11 or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are all rows the same length, and can the grid be empty? Are the values non-negative, or can they be negative? Are moves limited to right and down? Do the start and end cells count toward the total? Do you want only the cost, or the path as well? How big can the grid get, and may I change it?
I would assume a rectangular grid, moves only right and down, both end cells counted, only the total cost returned, and an empty grid giving 0. I would also leave the input untouched and use a single row of extra memory.
Brute force
Say the obvious answer and why it is too slow.
Recursion: from a cell, try the cost of going right and the cost of going down, and take the cheaper one. Without remembering anything, that explores every path. A grid with R rows and C columns has C(R+C-2, R-1) paths, which is exponential: a 20 by 20 grid already has about 35 billion paths, and a 200 by 200 grid has more than 10^100.
The recursion is slow because it keeps solving the same question again. Many different paths pass through the same cell, and each time the cheapest way to finish from that cell is worked out from scratch.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(2^(R+C))
- Time
- O(R×C)
- Space
- O(C)
The pattern is 2D dynamic programming on a grid. Define best(r, c) as the cheapest total of any path from the start to cell (r, c). A path can only arrive from the cell above or the cell to the left, so best(r, c) = grid[r][c] + min(best(r-1, c), best(r, c-1)).
Why this is correct: take an optimal path to (r, c), and look at the cell just before the last step. The part of the path up to that cell must itself be a cheapest path to it. If a cheaper one existed, you could swap it in and lower the total, and that swap is legal because what comes after the cell does not depend on how you reached it. So each answer is built from two smaller answers, and every cell is computed once.
Fill the table row by row, left to right, so the cell above and the cell to the left are ready when needed. Only the previous row matters, so one array of length C is enough: when you reach column c, best[c] still holds the value from the row above, and best[c-1] has already been updated to the current row, so it is the value from the left. Seed the array as [0, infinity, infinity, ...] so the first row and first column need no special cases. The answer is the last entry. I would say it aloud as: the cheapest way to reach a cell is its own value plus the cheaper of the two ways in.
Walk it through
A dry run on the example, step by step.
| Cell | Value | Above | Left | Array after |
|---|---|---|---|---|
| (0,0) | 2 | 0 (seed) | none | [2, inf, inf] |
| (0,1) | 1 | inf | 2 | [2, 3, inf] |
| (0,2) | 3 | inf | 3 | [2, 3, 6] |
| (1,0) | 4 | 2 | none | [6, 3, 6] |
| (1,1) | 8 | 3 | 6 | [6, 11, 6] |
| (1,2) | 1 | 6 | 11 | [6, 11, 7] |
| (2,0) | 7 | 6 | none | [13, 11, 7] |
| (2,1) | 2 | 11 | 13 | [13, 13, 7] |
| (2,2) | 1 | 7 | 13 | [13, 13, 8] |
Use [[2,1,3],[4,8,1],[7,2,1]]. The array starts as [0, inf, inf]; the trace table shows each cell, the two ways in and the array after the update.
Row 0 builds the running sums 2, 3, 6, because only "from the left" is possible. In row 1, cell (1,0) can only come from above: 2 + 4 = 6. Cell (1,1) has 3 above and 6 to the left, so 8 + 3 = 11. Cell (1,2) has 6 above and 11 to the left: 1 + 6 = 7. In row 2, cell (2,0) is 6 + 7 = 13, cell (2,1) is 2 + min(11, 13) = 13, and cell (2,2) is 1 + min(7, 13) = 8. The answer is 8.
The code
Runnable JavaScript, checked against test cases.
function minPathSum(grid) {
if (grid.length === 0 || grid[0].length === 0) return 0;
const cols = grid[0].length;
const best = new Array(cols).fill(Infinity);
best[0] = 0;
for (const row of grid) {
for (let c = 0; c < cols; c++) {
const fromAbove = best[c];
const fromLeft = c > 0 ? best[c - 1] : Infinity;
best[c] = row[c] + Math.min(fromAbove, fromLeft);
}
}
return best[cols - 1];
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
A one-cell grid returns that cell's value: the seed 0 plus the cell. A single row or single column forces one path, and the infinity entries make the sum happen automatically with no special code. An empty grid, or one with empty rows, is guarded and returns 0.
Zeros are fine. Ties between above and left are fine because only the minimum value is used. Non-square grids work because the row length is taken from the grid itself. The input array is read but never written. The DP only moves right and down, so it has no cycles, and the same recurrence would even handle negative values; non-negative values matter only if you later allow moves in all four directions.
Follow-ups to expect
Where the interviewer pushes next.
- How would you also return the path itself, and what extra memory does that need?
- What changes if you may also move left and up, and which algorithm replaces the DP?
- How would you count how many different paths reach the minimum total?
- What if some cells are blocked and cannot be entered?
- How would you cut memory to O(min(rows, columns)) for a very wide or very tall grid?
Where candidates slip
The mistakes this problem punishes.
The tempting wrong answer is greedy: from each cell step to the cheaper of the two neighbors. It fails because a cheap-looking cell can lead into an expensive region while a slightly dearer neighbor opens a cheap route.
Table slips: forgetting to include the starting cell's value, or counting it twice; special-casing the first row and column inconsistently so a border cell reads a missing neighbor; and, with a single row, mixing up which entry means "above" and which means "left" after overwriting in place. Others swap rows and columns on non-square grids, return the wrong corner, or write the plain recursion without memoization, which passes the sample and times out on a 30 by 30 grid.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.