Minimum Path Sum

Share

Given m x n grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum. You can only move right or down.

Example 1
Input: [[1,3,1],[1,5,1],[4,2,1]] → Output: 7
Example 2
Input: [[1,2,3],[4,5,6]] → Output: 12

Solution Approach

DP in-place: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j].

  • Initialize first row and column as prefix sums.
  • For i,j from 1 to m,n: dp[i][j] = min(from_above, from_left) + grid[i][j].
  • Return dp[m-1][n-1].
Java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
        for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        return grid[m-1][n-1];
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(1) in-place