Count maximum path in grid

Question

Given a grid represented by a 2D matrix, where each cell contains a non-negative integer representing the cost to enter that cell, count the maximum path sum from the top-left corner to the bottom-right corner of the grid, moving only down or right. The output should be a single integer representing the maximum path sum.

Codemia · Accepted Answer

This problem can be classified under dynamic programming because it requires us to build up a solution based on previously computed results. The goal is to find the maximum path sum from the top-left corner to the bottom-right corner of the grid while only moving down or right. The problem has overlapping subproblems; for instance, the maximum path sum to cell (i, j) depends on the maximum path sums to (i-1, j) and (i, j-1). By storing these intermediate results, we can avoid redundant calculations.

1. **Initialize a 2D DP array**: Create a DP array of the same dimensions as the grid to store maximum path sums up to each cell.
2. **Base Case**: Set the starting point DP[0][0] equal to grid[0][0]. This represents the cost of entering the top-left corner.
3. **Fill the First Row and First Column**: For the first row, the only way to move is from the left, so DP[0][j] = DP[0][j-1] + grid[0][j]. For the first column, movement is only from above, so DP[i][0] = DP[i-1][0] + grid[i][0].
4. **Fill the DP Table**: For each cell, the maximum path sum can be calculated as:
   DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + grid[i][j]. This means we take the maximum of the path sums from the left and above, and add the cost of the current cell.
5. **Return the Result**: The result will be in DP[m-1][n-1], where m and n are the dimensions of the grid.

Here is the Python implementation of the described approach:
```python
def maxPathSum(grid):
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

# Fill the first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

# Fill the first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

# Fill the rest of the dp array
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

return dp[m-1][n-1]
```
This code initializes the DP table, fills it accordingly, and finally returns the maximum path sum.

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because we are iterating through each cell in the grid exactly once. The space complexity is also O(m * n) due to the additional DP array. However, we can optimize the space complexity to O(n) by only storing the current and previous rows since each cell only depends on its left and upper neighbors.

1. **Empty Grid**: If the grid is empty, the function should return 0.
2. **Single Cell Grid**: If the grid contains only one cell, return the value of that cell.
3. **One Row or One Column**: If the grid is either one row or one column, the maximum path sum will be the sum of all elements in that row or column.
4. **Large Values**: Ensure that the implementation can handle large integers for costs without overflow issues (Python handles large integers gracefully).

Count maximum path in grid

Waymo

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Waymo Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string