The cheapest walk across a grid
grid has m rows and n columns, and grid[i][j] is the cost of passing through that cell.
Start in the top-left cell and finish in the bottom-right one, moving only one cell right or one cell down at a time. Return the smallest total cost of the cells on your way, counting the first and the last cell.
- Input
grid = [[1,4,2],[3,2,6],[5,1,1]]- Output
8
Down, right, down, right: 1 + 3 + 2 + 1 + 1.
- Input
grid = [[5,0,9]]- Output
14
With one row the only way is straight across.
Limits
1 <= m, n <= 2000 <= grid[i][j] <= 1000
Hints
Hint 1
The cheapest way into a cell comes either from above or from the left, whichever is cheaper.
Hint 2
Fill the costs row by row; one row of them is all you need to keep.
Where this was reported
- Amazon, SDE-1 fresher interview, 2025 (LeetCode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
