UIREADY.dev
Minimum Path SumLoading saved progress…

Minimum Path Sum

The minimum path sum of a grid is the smallest total you can collect while walking from the top-left cell to the bottom-right cell when every step must move either one cell right or one cell down. This is LeetCode 64, a classic first taste of dynamic programming: the cheapest way to reach any cell is built from the cheapest ways to reach the two cells that feed into it. You are given a rectangular grid of non-negative numbers and return that minimum sum — the number itself, not the path that produces it.

Signature

minPathSum(grid)   // grid: number[][], non-empty, non-negative  ->  number

Examples

// The classic 3x3: the path 1 -> 3 -> 1 -> 1 -> 1 collects the least, 7.
minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]); // 7
// A single row has only one possible path, so you sum every cell.
minPathSum([[1, 2, 3]]); // 6
// A 2x2 grid: drop straight down then right (1 -> 1 -> 1) and skip the 2.
minPathSum([[1, 2], [1, 1]]); // 3

Notes

  • Down or right only — from cell (i, j) you may step to (i + 1, j) or (i, j + 1). No diagonals, and never up or left.
  • Non-negative numbers — every cell is >= 0. Values can repeat, and a grid of all zeros costs 0.
  • Non-empty grid — there is at least one row and one column. A 1x1 grid's answer is simply its single cell.
  • Return the sum, not the path — you return the minimum total as a number; you do not need to report which cells it walked through.
  • Leave the input alone — build your own scratch storage for the running costs; do not overwrite grid, since a caller may reuse it.

FAQ

What is the time and space complexity?
The dynamic-programming solution fills each of the m by n cells exactly once with constant work, so it runs in O(m*n) time and O(m*n) space. The space drops to O(n) if you keep only one row, since each cell depends only on the row above and the cell to its left.
Why does allowing only down and right moves make this tractable?
With only down and right moves the grid is acyclic and every cell has exactly two possible predecessors — the cell above and the cell to the left — so you can fill the table in a single top-left-to-bottom-right pass. Allowing up or left moves would create cycles and call for Dijkstra's shortest-path algorithm instead.
Can't you just greedily step toward the smaller neighbour each time?
No. Choosing the cheaper next cell at each step can walk you into an expensive region later and miss the true minimum. You have to weigh whole routes, which is exactly what the dp table does by remembering the best cost to reach every cell.
Loading editor…