Minimum Path Sum

NeetCode: Minimum Path Sum · LeetCode: 64. Minimum Path Sum · Difficulty: Medium

Given an m x n grid (int[][]) of non-negative integers, find a path from the top-left cell to the bottom-right cell that minimizes the sum of the numbers along the path. You may only move right or down. Return that minimum sum.

Example

Text

Input:  grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]    Output: 7    (1 -> 3 -> 1 -> 1 -> 1)
Input:  grid = [[1, 2, 3], [4, 5, 6]]               Output: 12   (1 -> 2 -> 3 -> 6)

Brute force: plain recursion

The cheapest way to finish from cell (i, j) is the cell's own value plus the cheaper of the cheapest finish from the cell to the right and from the cell below. At the bottom-right cell the path ends. Trying both moves everywhere explores every path, and there are C(m + n - 2, m - 1) of them, which is exponential (O(2^(m+n))). The recursion is slow because it recomputes the same cell's answer once for every path that reaches it.

Java

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        return go(grid, 0, 0);
    }

    private int go(int[][] g, int i, int j) {
        int m = g.length, n = g[0].length;
        if (i == m - 1 && j == n - 1) return g[i][j];
        int best = Integer.MAX_VALUE;
        if (i + 1 < m) best = Math.min(best, go(g, i + 1, j));
        if (j + 1 < n) best = Math.min(best, go(g, i, j + 1));
        return g[i][j] + best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
        System.out.println(s.minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
        System.out.println(s.minPathSum(new int[][]{{7}}));
    }
}

Output

7
12
7

Time: O(2^(m+n)). Space: O(m + n) recursion depth.

Better: memoization

There are only m * n distinct cells, so cache the answer for each one. Every cell is now solved once, in O(1) after its two neighbours are known. The cache is an int[][] filled with -1, which cannot be a real answer because every value is non-negative.

Java

import java.util.Arrays;

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int[][] memo = new int[grid.length][grid[0].length];
        for (int[] row : memo) Arrays.fill(row, -1);
        return go(grid, 0, 0, memo);
    }

    private int go(int[][] g, int i, int j, int[][] memo) {
        if (memo[i][j] != -1) return memo[i][j];
        int m = g.length, n = g[0].length;
        int res;
        if (i == m - 1 && j == n - 1) {
            res = g[i][j];
        } else {
            int best = Integer.MAX_VALUE;
            if (i + 1 < m) best = Math.min(best, go(g, i + 1, j, memo));
            if (j + 1 < n) best = Math.min(best, go(g, i, j + 1, memo));
            res = g[i][j] + best;
        }
        memo[i][j] = res;
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
        System.out.println(s.minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
        System.out.println(s.minPathSum(new int[][]{{7}}));
    }
}

Output

7
12
7

Time: O(m * n). Space: O(m * n).

Optimal: one-row DP

Flip the direction: let dp[i][j] be the cheapest sum of a path from the start to (i, j). A cell can only be entered from above or from the left, so dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Row i only needs row i - 1, so a single array is enough: when visiting (i, j), dp[j] still holds the value from above and dp[j-1] already holds the value from the left.

Java

import java.util.Arrays;

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid[0].length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[0] = grid[0][0];
                    continue;
                }
                int fromAbove = dp[j];                            // MAX_VALUE in the first row
                int fromLeft = j > 0 ? dp[j - 1] : Integer.MAX_VALUE;
                dp[j] = grid[i][j] + Math.min(fromAbove, fromLeft);
            }
        }
        return dp[n - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
        System.out.println(s.minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
        System.out.println(s.minPathSum(new int[][]{{7}}));
    }
}

Output

7
12
7

Time: O(m * n). Space: O(n).

Integer.MAX_VALUE marks "unreachable". int addition wraps silently on overflow, so the code must never add to MAX_VALUE. That cannot happen here: for every cell except the start, at least one of fromAbove and fromLeft is a real sum, so the minimum is never MAX_VALUE. The start cell is handled separately. With the problem's limits, real sums fit in int.