algoadvance

Leetcode 64. Minimum Path Sum

Problem Statement

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.

Clarifying Questions

1. Q: What should I return if the input grid is empty? A: You can assume the grid will always have at least one cell.

2. Q: Is there any constraint on the values inside the grid? A: The grid will always contain non-negative integers only.

3. Q: Can you move diagonally? A: No, you can only move either down or right.

Strategy

To solve this problem, we can use Dynamic Programming (DP). The idea is to construct a dp table where dp[i][j] contains the minimum path sum to reach cell (i, j).

Here’s the strategy:

1. Initialization:
   • The top-left cell dp[0][0] is simply the grid’s top-left cell value.
   • Fill in the first row where dp[0][j] = dp[0][j-1] + grid[0][j] since you can only move right.
   • Fill in the first column where dp[i][0] = dp[i-1][0] + grid[i][0] since you can only move down.
2. Filling the DP Table:
   • For other cells, dp[i][j] is the minimum of the value coming from the top or the left, plus the current cell’s value: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
3. Result:
   • The value at the bottom-right cell dp[m-1][n-1] will be the minimum path sum.

Code

Here is the implementation in Java:

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        // Initialize the DP table with the grid's array values.
        dp[0][0] = grid[0][0];
        
        // Fill in the first row.
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        
        // Fill in the first column.
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        
        // Fill in the rest of the DP table.
        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]);
            }
        }
        
        // The answer is in the bottom-right cell.
        return dp[m-1][n-1];
    }
}

Time Complexity

• Time Complexity: The time complexity is (O(m \times n)), where (m) is the number of rows and (n) is the number of columns. This is because we fill each cell of the dp table exactly once.

• Space Complexity: The space complexity is (O(m \times n)) due to the additional dp array of the same size as the grid. However, it can be optimized to (O(n)) by using a single-dimensional array if needed.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?