algoadvance

Leetcode 64. Minimum Path Sum

Problem Statement

Given a m x n grid filled with non-negative numbers, find a path from the top left to the 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. Is the input grid always valid and non-empty?
   • Yes, you can assume the grid always has at least one cell.
2. Can the grid contain zero values?
   • Yes, any non-negative number, including zero, can be part of the grid values.
3. Are there any restrictions on the grid size?
   • For this problem, there are no specific size restrictions mentioned, but typical considerations for computational limits (like constraints often seen in competitive programming problems) should be assumed.

Strategy

This problem can be efficiently solved using Dynamic Programming (DP). Here’s the strategy:

1. Define a DP Table:
   • We’ll use a 2D vector dp where dp[i][j] will store the minimum path sum to reach the cell (i, j).
2. Initialize the DP Table:
   • dp[0][0] will just be grid[0][0] as it is the starting point.
   • The first row dp[0][j] can only be reached from the left, so we sum up values from the leftmost column.
   • The first column dp[i][0] can only be reached from the top, so we sum up values from the topmost row.
3. Fill the DP Table:
   • For each cell (i, j), the minimum path sum can be found by taking the minimum of the paths coming from the top (dp[i-1][j]) or from the left (dp[i][j-1]).
4. Return the Result:
   • The value in dp[m-1][n-1] will be the minimum path sum to reach the bottom-right corner.

Code

Here’s the implementation of the above strategy:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        dp[0][0] = grid[0][0];
        
        // Initialize the first row
        for (int j = 1; j < n; ++j) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        
        // Initialize the first column
        for (int i = 1; i < m; ++i) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        
        // Fill the rest of the dp table
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        
        return dp[m-1][n-1];
    }
};

Time Complexity

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. We are iterating through each cell in the grid once.
• Space Complexity: O(m * n) for the DP table. However, the space complexity can be optimized to O(n) by using a single row for the DP computation since we only need the current and the previous row to calculate the minimum path sum at any cell.

This approach ensures optimal performance while respecting constraints typical of competitive programming problems.

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?