algoadvance

Leetcode 3248. Snake in Matrix

Problem Statement

You are given an m x n matrix grid consisting of non-negative integers. We need to find and return the path, starting from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) with the maximum sum of integers. The path can only move either down or right at any point in time.

Here is a summary:

Clarifying Questions

  1. Is it guaranteed that m and n will always be greater than or equal to 1?
    • Yes.
  2. Are there any constraints on the values within the grid?
    • All integers are non-negative, and all values in the grid fall within the range from 0 to a large value.
  3. Should we consider the case of moving diagonally?
    • No, movement is strictly down or right.

Strategy

We will use dynamic programming to solve this problem by creating a dp table where dp[i][j] will store the maximum sum of the path from the top-left to the cell (i, j). The recurrence relation can be defined as:

[ dp[i][j] = \text{grid}[i][j] + \max(dp[i-1][j], dp[i][j-1]) ]

Where:

Initial conditions:

Boundary conditions should handle the first row and first column separately since they only have one valid incoming direction (from the left or from above, respectively).

Code

Here is the C++ implementation:

#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    int maxPathSum(std::vector<std::vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        // If the grid dimensions are less than required, return 0.
        if(m == 0 || n == 0) return 0;

        // Create a DP table with the same dimensions as the grid.
        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));

        // Initialize the starting point.
        dp[0][0] = grid[0][0];

        // Fill the first row.
        for(int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        // Fill 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] = grid[i][j] + std::max(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];
    }
};

// Example of running the code.
int main() {
    Solution solution;
    std::vector<std::vector<int>> grid = {
        {5, 3, 2, 1},
        {1, 7, 1, 8},
        {4, 6, 5, 2},
        {1, 2, 3, 4}
    };
    int result = solution.maxPathSum(grid);
    std::cout << "The maximum path sum is: " << result << std::endl;
    return 0;
}

Time Complexity

The time complexity of this approach is (O(m \times n)), where m is the number of rows and n is the number of columns in the grid. This is because we need to fill each cell in the dp table once.

The space complexity is also (O(m \times n)) due to the additional storage for the dp table.

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