Obsidian Notes

Minimum Path Sum

4 min read

Description

Minimum Path Sum

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.

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

Example 1:

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:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

Approach - Bottom Up 1D DP

  • put nth element as infinity and base condition rest is easy dp[j] means what is the value at dp[i-1][j] top left and dp[j+1] is bottom right
class Solution {
    public int minPathSum(int[][] grid) {
        int r = grid.length, c = grid[0].length;
        int[] dp = new int[c+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[c-1] = 0;
 
        for (int i = r - 1; i >= 0; i--) {
            for (int j = c - 1; j >=0; j--) {
                dp[j] = grid[i][j] + Math.min(dp[j],dp[j+1]);
            }
        }
 
        return dp[0];
    }
}

Primary Approach: In-Place 2D Dynamic Programming ( Time, Space)

Intuition

To solve 64. Minimum Path Sum, note that movement is restricted strictly to moving down or right. Therefore, the minimum path sum to reach cell (r, c) depends solely on the minimum path sum of its top neighbor (r - 1, c) or its left neighbor (r, c - 1):

Instead of allocating extra matrix memory, we can modify the input grid in-place:

  1. Initialize grid[0][0] as itself.
  2. Fill the first row: grid[0][c] += grid[0][c - 1] (can only be reached from the left).
  3. Fill the first column: grid[r][0] += grid[r - 1][0] (can only be reached from above).
  4. For all remaining cells (r, c), update grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]).
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
 
        // Fill top row (can only arrive from left)
        for (int c = 1; c < n; c++) {
            grid[0][c] += grid[0][c - 1];
        }
 
        // Fill left column (can only arrive from above)
        for (int r = 1; r < m; r++) {
            grid[r][0] += grid[r - 1][0];
        }
 
        // Fill rest of the grid
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
            }
        }
 
        return grid[m - 1][n - 1];
    }
}

Complexity

  • Time Complexity: — Single pass through every cell in the grid.
  • Space Complexity: auxiliary space — Mutates the input grid directly in-place without additional memory allocations.

Alternative Approach: 1D Space-Optimized DP ( Time, Space)

Intuition

If modifying the input matrix is not allowed (e.g., read-only memory), we can reduce space to a single 1D array because computing the current row only requires values from the previous row and the left cell:

  1. Maintain a 1D array dp of size representing the current row’s min path sums.
  2. Initialize dp[0] = grid[0][0] and fill the rest of row 0.
  3. For each subsequent row, dp[c] before updating represents the cell directly above (r - 1, c), while dp[c - 1] represents the updated cell to the left (r, c - 1).
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
 
        dp[0] = grid[0][0];
        for (int c = 1; c < n; c++) {
            dp[c] = dp[c - 1] + grid[0][c];
        }
 
        for (int r = 1; r < m; r++) {
            dp[0] += grid[r][0]; // Update first column cell from above
            for (int c = 1; c < n; c++) {
                dp[c] = grid[r][c] + Math.min(dp[c], dp[c - 1]);
            }
        }
 
        return dp[n - 1];
    }
}

Complexity

  • Time Complexity: — Visits every cell once.
  • Space Complexity: auxiliary space — Requires a 1D array bounded by the number of columns .

Key Interview Discussion Points

  • Read-Only Input Constraint: Always clarify with the interviewer if modifying the original grid array in-place is permissible. If immutable inputs are required, present the 1D DP array.
  • Why DP Over Dijkstra: While shortest path algorithms like Dijkstra can find path sums on general graphs in , a DAG with unidirectional movements (Down & Right) allows standard Dynamic Programming without priority queue overhead.

Easy Memory Rule

“Can only move Down or Right grid[r][c] += min(Above, Left)!”

Backlinks