Minimum Path Sum

medium2D Dynamic Programming53 stepsJava · Python · C++

Find the cheapest path from top-left to bottom-right moving right or down, where each cell has a cost. The cheapest way into a cell is its cost plus the cheaper of the cell above and the cell to the left.

▶ Watch the animated trace

Traced input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] → 7. Original problem: neetcode.io/problems/minimum-path-sum

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(1)

Overwrites the grid in place.

Key idea

grid[r][c] += min(top, left), with the borders having only one option.
Filling row by row guarantees both neighbours are already final.
Doing it in place saves memory, but mutates the input.

Common mistakes

Forgetting the first row and first column have only one neighbour.
Greedily picking the cheaper next cell fails.

Solution

Java

int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (r == 0 && c == 0) continue;
            int top = r > 0 ? grid[r - 1][c] : Integer.MAX_VALUE;
            int left = c > 0 ? grid[r][c - 1] : Integer.MAX_VALUE;
            grid[r][c] += Math.min(top, left);
        }
    }
    return grid[m - 1][n - 1];
}

Python

def minPathSum(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0: continue
            top = grid[r - 1][c] if r > 0 else float("inf")
            left = grid[r][c - 1] if c > 0 else float("inf")
            grid[r][c] += min(top, left)
    return grid[m - 1][n - 1]

C++

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (r == 0 && c == 0) continue;
            int top = r > 0 ? grid[r - 1][c] : INT_MAX;
            int left = c > 0 ? grid[r][c - 1] : INT_MAX;
            grid[r][c] += min(top, left);
        }
    }
    return grid[m - 1][n - 1];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single cell Just its own cost.	`grid = [[5]]`	`5`
Single row Sum of the row.	`grid = [[1, 2, 3]]`	`6`
Zeros Every path costs 0.	`grid = [[0, 0], [0, 0]]`	`0`