Algorithm Day93 - Minimum Path Sum

Posted on In , Views:

🧩 Problem Description

Given a m x n grid filled with non-negative numbers, find a path from top-left to bottom-right, which minimizes the sum of all numbers along its path.

You can only move either down or right at any point in time.

💬 Examples

Example 1

1
2
3
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2

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

💡 Intuition

This is a classic dynamic programming problem on a grid.
At each cell (i, j), the minimum path sum equals the cell value plus the smaller of the top or left neighbor:

1
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

We can compute this iteratively using either a 2D or 1D DP array.

🔢 Java Code (2D DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        
        for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

🔢 Java Code (1D DP Optimization)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        
        for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
        
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
            }
        }
        return dp[n - 1];
    }
}

⏱ Complexity Analysis

  • Time: O(m × n)
  • Space: O(n) (after optimization)

✍️ Summary

  • Classic DP grid problem.
  • Choose minimum between top and left cells.
  • Can be optimized to 1D array.

Related problems:

  • lc-62 (Unique Paths)
  • lc-63 (Unique Paths II)
  • lc-120 (Triangle)