Minimum Path Sum

Medium Problem 128 of 151 Java and Python

Problem

Given an m × n grid of non-negative numbers, find a path from the top-left to the bottom-right that minimises the sum of the numbers along it. You can only move right or down.

Example 1

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Why: The path 1 → 3 → 1 → 1 → 1.

Example 2

Input: grid = [[1, 2, 3], [4, 5, 6]]
Output: 12

Constraints

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

Explanation

Like Unique Paths, but instead of adding the counts from above and left, take the cheaper of the two and add the current cell.

Approach 1 · Naive

Plain recursion

Time O(2^(m + n))
Space O(m + n)

The best cost to a cell is its value plus the cheaper of the best costs above and to the left.

cost(0, 0) = grid[0][0]; out-of-grid is infinity.
cost(r, c) = grid[r][c] + min(cost(r - 1, c), cost(r, c - 1)).

Java

class Solution {
    public int minPathSum(int[][] grid) {
        return cost(grid, grid.length - 1, grid[0].length - 1);
    }

    private int cost(int[][] grid, int r, int c) {
        if (r == 0 && c == 0) {
            return grid[0][0];
        }
        if (r < 0 || c < 0) {
            return Integer.MAX_VALUE;
        }
        int best = Math.min(r > 0 ? cost(grid, r - 1, c) : Integer.MAX_VALUE, c > 0 ? cost(grid, r, c - 1) : Integer.MAX_VALUE);
        return grid[r][c] + best;
    }
}

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        def cost(r, c):
            if r == 0 and c == 0:
                return grid[0][0]
            if r < 0 or c < 0:
                return float("inf")
            return grid[r][c] + min(cost(r - 1, c), cost(r, c - 1))

        return cost(len(grid) - 1, len(grid[0]) - 1)

Approach 2 · Optimal

DP with one row

Time O(m · n)
Space O(n)

Keep the best costs for the current row. Each cell takes the min of the value above (old entry) and to the left (just updated).

Fill the first row with running sums.
For each next row: row[0] += grid[r][0]; for c ≥ 1, row[c] = grid[r][c] + min(row[c], row[c - 1]).
Return row[n - 1].

Java

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] row = new int[n];
        row[0] = grid[0][0];
        for (int c = 1; c < n; c++) {
            row[c] = row[c - 1] + grid[0][c];
        }
        for (int r = 1; r < grid.length; r++) {
            row[0] += grid[r][0];
            for (int c = 1; c < n; c++) {
                row[c] = grid[r][c] + Math.min(row[c], row[c - 1]);
            }
        }
        return row[n - 1];
    }
}

Python

from itertools import accumulate

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        row = list(accumulate(grid[0]))
        for r in range(1, len(grid)):
            row[0] += grid[r][0]
            for c in range(1, len(row)):
                row[c] = grid[r][c] + min(row[c], row[c - 1])
        return row[-1]

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2^(m + n))	O(m + n)
Optimal DP with one row	O(m · n)	O(n)

Key takeaways

Counting paths uses +; finding the best path uses min/max. The table shape is the same.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem