The cheapest path through a grid
A grid of non-negative integers gives the cost of each cell. Starting at the top-left cell and moving only right or down, reach the bottom-right cell. Return the smallest total cost of the cells on the path, including both ends.
Examples
| Input | Output | Why |
|---|---|---|
grid = [[1,3,1],[1,5,1],[4,2,1]] | 7 | 1 → 3 → 1 → 1 → 1. |
grid = [[1,2,3],[4,5,6]] | 12 | 1 → 2 → 3 → 6. |
grid = [[7]] | 7 | One cell. |
Constraints
- 1 ≤ rows, cols ≤ 200
- 0 ≤ grid[r][c] ≤ 200
Hints
Hint 1
The last move into a cell came from above or from the left.
Hint 2
dp[r][c] = grid[r][c] + min(dp[r − 1][c], dp[r][c − 1]), with the first row and column having only one option.
Hint 3
One row of length cols is enough.
Where people lose marks
- Using Dijkstra or breadth-first search: correct but unnecessary when moves are only right and down.
- Treating the first row or column as reachable from outside the grid.
Dry run on [[1,3,1],[1,5,1],[4,2,1]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 9
Base cases filled first.
-
Step 2 / 9
(0, 1): 3 + min(—, 1) = 4.
-
Step 3 / 9
(0, 2): 1 + min(—, 4) = 5.
-
Step 4 / 9
(1, 0): 1 + min(1, —) = 2.
-
Step 5 / 9
(1, 1): 5 + min(4, 2) = 7.
-
Step 6 / 9
(1, 2): 1 + min(5, 7) = 6.
-
Step 7 / 9
(2, 0): 4 + min(2, —) = 6.
-
Step 8 / 9
(2, 1): 2 + min(7, 6) = 8.
-
Step 9 / 9
(2, 2): 1 + min(6, 8) = 7. The answer is 7.
How to think about it
Moves only go right and down, so a cell's cheapest arrival depends only on the cell above and the cell to the left,
both earlier in row-major order: dp[r][c] = grid[r][c] + min(dp[r − 1][c], dp[r][c − 1]). The first row can only
be reached from the left and the first column only from above. Updating a single row in place works, because
row[c] still holds the value from above when it is read, and row[c − 1] has just been
updated.
Complexity. Time O(rows · cols) · Space O(cols)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_path_sum(grid):
cols = len(grid[0])
row = [float('inf')] * cols # dp for the row above; nothing above row 0
row[0] = 0
for r in range(len(grid)):
for c in range(cols):
left = row[c - 1] if c > 0 else float('inf')
row[c] = grid[r][c] + min(row[c], left) # row[c] still holds the cell above
return row[cols - 1]#include <algorithm>
#include <climits>
#include <vector>
long long solve(const std::vector<std::vector<int>>& grid) {
const int cols = grid[0].size();
const long long INF = LLONG_MAX / 4;
std::vector<long long> row(cols, INF);
row[0] = 0;
for (const auto& line : grid)
for (int c = 0; c < cols; ++c) row[c] = line[c] + std::min(row[c], c > 0 ? row[c - 1] : INF); // above, left
return row[cols - 1];
}class Solution {
public long minPathSum(int[][] grid) {
int cols = grid[0].length;
long inf = Long.MAX_VALUE / 4;
long[] row = new long[cols];
java.util.Arrays.fill(row, inf);
row[0] = 0;
for (int[] line : grid)
for (int c = 0; c < cols; c++) row[c] = line[c] + Math.min(row[c], c > 0 ? row[c - 1] : inf); // above, left
return row[cols - 1];
}
}function minPathSum(grid) {
const cols = grid[0].length, row = new Array(cols).fill(Infinity);
row[0] = 0;
for (const line of grid)
for (let c = 0; c < cols; c++) row[c] = line[c] + Math.min(row[c], c > 0 ? row[c - 1] : Infinity); // above, left
return row[cols - 1];
}fn solve<const C: usize>(grid: &[[i64; C]]) -> i64 {
let inf = i64::MAX / 4;
let mut row = [inf; C];
row[0] = 0;
for line in grid {
for c in 0..C {
let left = if c > 0 { row[c - 1] } else { inf };
row[c] = line[c] + row[c].min(left); // row[c] is still the cell above
}
}
row[C - 1]
}solve :: [[Int]] -> Int
solve (first : rest) = last (foldl nextRow (scanl1 (+) first) rest)
where
-- each cell: its cost plus the cheaper of the cell above and the cell just computed to its left
nextRow above line = tail (scanl (\left (cost, up) -> cost + min left up) maxBound (zip line above))
solve [] = 0Variants to try
- Return the path.
- Moves in all four directions: Dijkstra.
- Collect the maximum instead, or require two non-crossing paths (cherry pickup).
Next problems
Paths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Medium20 minThe largest square of ones
Find the area of the largest all-ones square in a 0/1 grid. The square ending at a cell is limited by the three squares ending next to it.
Open the problem → Hard30 minThe least starting health
Cross a grid of gains and losses, right or down, without health ever dropping to zero. The requirement at a cell depends on what comes after, so fill from the end.
Open the problem →Write a solution and run it against the real test table.
Keep going
Paths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Medium20 minThe largest square of ones
Find the area of the largest all-ones square in a 0/1 grid. The square ending at a cell is limited by the three squares ending next to it.
Open the problem → Hard30 minThe least starting health
Cross a grid of gains and losses, right or down, without health ever dropping to zero. The requirement at a cell depends on what comes after, so fill from the end.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.