Greedy on grid

Question

Given a 2D grid filled with non-negative integers, your task is to find the maximum sum of values you can collect while moving from the top-left corner to the bottom-right corner, only being allowed to move right or down at each step. Implement a greedy algorithm to determine the optimal path and return the maximum sum as the output.

Codemia · Accepted Answer

The problem presents a grid traversal challenge where we want to maximize the sum of values collected from the top-left corner to the bottom-right corner by only moving right or down. This scenario suggests a dynamic programming approach, where we can build an optimal solution from previously computed states. The greedy aspect comes into play as we prioritize the highest values at each step along the path. The key is to recognize that for any cell `(i, j)`, the maximum sum to reach that cell can be computed from the maximum sums of the cells directly above it `(i-1, j)` and to the left of it `(i, j-1)`. Thus, we can use a 2D array to store the maximum sums at each cell as we iterate through the grid.

1. **Initialize a 2D list** `dp` of the same dimensions as the grid to store the maximum sums. 
2. **Set the starting point**: `dp[0][0] = grid[0][0]`. 
3. **Fill the first row**: Since you can only move from left to right in the first row, each cell `dp[0][j] = dp[0][j-1] + grid[0][j]`. 
4. **Fill the first column**: Similarly, for the first column, each cell `dp[i][0] = dp[i-1][0] + grid[i][0]`. 
5. **Fill the rest of the dp array**: For each cell `(i, j)`, calculate `dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])`, meaning you take the current grid value and add the maximum of the sums from the cell above or to the left. 
6. **Return the value at the bottom-right corner**: `dp[m-1][n-1]` will contain the maximum sum.

```python
def max_sum_path(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]

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

for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])

return dp[m-1][n-1]
```

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 process each cell exactly once. The space complexity is also O(m * n) due to the storage of the dp array. However, this can be optimized to O(n) by only storing the current and previous rows, since we only ever need the values from the row above and the current row.

1. **Empty Grid**: If the grid is empty or has no columns, the output should be 0. 
2. **Single Cell Grid**: If the grid is 1x1, the output should be the value of that single cell. 
3. **Larger Values**: Ensure that the solution handles large values correctly, especially if they might lead to integer overflow in some programming languages (though Python handles large integers well). 
4. **Rows or Columns of Zeros**: If a row or column of the grid contains zeros, the path should still calculate correctly, as it will rely on previous maximum sums.

Greedy on grid

Doordash

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

Doordash Software 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