#64 Minimum Path Sum

frequently reported atGoldman Sachs Microsoft Amazon Google

the problem

In plain words

Given an m × n grid of non-negative numbers, find a path from the top-left to the bottom-right (moving only right or down) with the smallest sum of numbers.

in grid = [[1,3,1],[1,5,1],[4,2,1]]

out 7

1→3→1→1→1.

in grid = [[1,2,3],[4,5,6]]

out 12

1 ≤ m, n ≤ 200
0 ≤ grid[i][j] ≤ 200

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGrid DP

The cheapest way into a cell = its own cost + the cheaper of the cheapest ways into the cell above and the cell to the left.

solutions

From brute force to optimal

best(r, c) = grid[r][c] + min(best(r−1, c), best(r, c−1)).

Start cell is the base case.
Edges have only one neighbour.

timeO(2^(m+n))

Two branches per step.

spaceO(m + n)

Recursion depth.

javajava.util.*

1class Solution {2    public int minPathSum(int[][] grid) {3        return best(grid, grid.length - 1, grid[0].length - 1);4    }5 6    /** Cheapest path sum from (0,0) to (r,c). */7    private int best(int[][] grid, int r, int c) {8        if (r == 0 && c == 0) return grid[0][0];9        if (r == 0) return grid[r][c] + best(grid, r, c - 1);10        if (c == 0) return grid[r][c] + best(grid, r - 1, c);11        return grid[r][c] + Math.min(best(grid, r - 1, c), best(grid, r, c - 1));12    }13}

Cache best(r, c); −1 = unknown (0 is a valid sum).

Check, compute, store.

timeO(m·n)

Each cell once.

spaceO(m·n)

Memo + stack.

javajava.util.*

1class Solution {2    public int minPathSum(int[][] grid) {3        int[][] memo = new int[grid.length][grid[0].length];4        for (int[] row : memo) Arrays.fill(row, -1);5        return best(grid, grid.length - 1, grid[0].length - 1, memo);6    }7 8    private int best(int[][] grid, int r, int c, int[][] memo) {9        if (r == 0 && c == 0) return grid[0][0];10        if (memo[r][c] != -1) return memo[r][c];11        int result;12        if (r == 0) result = grid[r][c] + best(grid, r, c - 1, memo);13        else if (c == 0) result = grid[r][c] + best(grid, r - 1, c, memo);14        else result = grid[r][c] + Math.min(best(grid, r - 1, c, memo), best(grid, r, c - 1, memo));15        return memo[r][c] = result;16    }17}

Fill row by row; edges come from one side only.

dp[0][0] = grid[0][0].
Top row from the left, left column from above.
Others: grid + min(up, left).

timeO(m·n)

One step per cell.

spaceO(m·n)

The table.

javajava.util.*

1class Solution {2    public int minPathSum(int[][] grid) {3        int m = grid.length, n = grid[0].length;4        int[][] dp = new int[m][n]; // dp[r][c] = cheapest sum to reach (r, c)5        for (int r = 0; r < m; r++) {6            for (int c = 0; c < n; c++) {7                if (r == 0 && c == 0) dp[r][c] = grid[0][0];8                else if (r == 0) dp[r][c] = dp[r][c - 1] + grid[r][c]; // top row: only from the left9                else if (c == 0) dp[r][c] = dp[r - 1][c] + grid[r][c]; // left column: only from above10                else dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);11            }12        }13        return dp[m - 1][n - 1];14    }15}

sim

Build the cost landscape

loading simulation…

javajava.util.*

1class Solution {2    public int minPathSum(int[][] grid) {3        int m = grid.length, n = grid[0].length;4        int[][] dp = new int[m][n]; // dp[r][c] = cheapest sum to reach (r, c)5        for (int r = 0; r < m; r++) {6            for (int c = 0; c < n; c++) {7                if (r == 0 && c == 0) dp[r][c] = grid[0][0];8                else if (r == 0) dp[r][c] = dp[r][c - 1] + grid[r][c]; // top row: only from the left9                else if (c == 0) dp[r][c] = dp[r - 1][c] + grid[r][c]; // left column: only from above10                else dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);11            }12        }13        return dp[m - 1][n - 1];14    }15}

dp[c] holds "above" before you overwrite it with the new value.

Fill the top row.
Each next row: dp[0] += grid[r][0]; dp[c] = grid[r][c] + min(dp[c], dp[c−1]).

timeO(m·n)

Same updates.

spaceO(n)

One row (or O(1) extra if you may overwrite grid).

javajava.util.*

1class Solution {2    public int minPathSum(int[][] grid) {3        int m = grid.length, n = grid[0].length;4        int[] dp = new int[n]; // dp[c] = cheapest sum to the cell in column c of the current row5        dp[0] = grid[0][0];6        for (int c = 1; c < n; c++) dp[c] = dp[c - 1] + grid[0][c]; // top row7        for (int r = 1; r < m; r++) {8            dp[0] += grid[r][0]; // left column: only from above9            for (int c = 1; c < n; c++) {10                dp[c] = grid[r][c] + Math.min(dp[c], dp[c - 1]); // dp[c] = above (old), dp[c-1] = left (new)11            }12        }13        return dp[n - 1];14    }15}

in the room

How to say it in the interview

talk track

Ask if you may modify the input grid — then you can store dp in it for O(1) extra space.

traps

Treating edge cells like inner cells reads out of bounds or a fake 0 neighbour.

what they ask next

Follow-ups

Moves in all 4 directions?

Then cells can depend on each other in cycles — use Dijkstra (non-negative costs), not grid DP.

before you submit

Edge cases to test

One cell → its value.
One row or one column → the sum of everything.
Zeros are allowed, so 0 can't mean "not computed" in a memo.

practise next