Dynamic Programming on matrix

Question

Given a matrix of integers, implement a dynamic programming solution to find the maximum path sum from the top-left corner to the bottom-right corner, where you can only move down or right. The function should return the maximum sum achievable along this path.

Codemia · Accepted Answer

The problem requires finding the maximum path sum in a matrix from the top-left corner to the bottom-right corner, moving only down or right. This hints at a dynamic programming approach because the solution can be built from previously computed results. Specifically, we can define a state, `dp[i][j]`, to represent the maximum sum achievable to reach cell `(i, j)`. The recurrence relation will be:

- If we move down to cell `(i, j)`, the maximum sum will be the value of the current cell plus the maximum of the sums from the cell above `(i-1, j)` or from the left `(i, j-1)`. Thus, the transition can be expressed as:

`dp[i][j] = matrix[i][j] + max(dp[i-1][j], dp[i][j-1])`

This approach leverages overlapping subproblems and optimal substructure, which are key characteristics of dynamic programming.

We will follow these steps to implement our solution:
1. **Initialization**: Create a 2D list `dp` of the same size as the input matrix, initialized to 0.
2. **Base Case**: Set `dp[0][0]` to `matrix[0][0]` since that is our starting point.
3. **Fill the First Row and Column**: Since we can only move right or down, fill the first row and first column:
   - For the first row, each cell is the sum of the current cell and the cell to its left.
   - For the first column, each cell is the sum of the current cell and the cell above it.
4. **Dynamic Programming Fill**: Use nested loops to fill in the `dp` table based on our recurrence relation, iterating from `1` to `m-1` for rows and `1` to `n-1` for columns.
5. **Return Result**: The maximum path sum will be stored in `dp[m-1][n-1]`.

**Example**: For a matrix `[[5, 3, 2], [1, 4, 6], [7, 1, 8]]`, we will compute `dp` as follows:
- Start with `dp[0][0] = 5`. 
- Fill the first row: `dp[0][1] = 8`, `dp[0][2] = 10`.
- Fill the first column: `dp[1][0] = 6`, `dp[2][0] = 13`.
- Complete the `dp` table, with the final value in `dp[2][2]` being the maximum path sum.

Here is the Python implementation of the solution:
```python
def maxPathSum(matrix):
    if not matrix or not matrix[0]:
        return 0  # Edge case for empty matrix
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = matrix[0][0]  # Starting point

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

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

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

return dp[m-1][n-1]  # Return the maximum path sum
```
This code effectively computes the desired maximum path sum in a structured manner.

The time complexity for this solution is O(m * n), where `m` is the number of rows and `n` is the number of columns in the matrix. This is because we iterate through each cell in the matrix once to fill the `dp` table. The space complexity is also O(m * n) due to the storage required for the `dp` array. However, we can optimize the space complexity to O(n) by only keeping the current and previous rows, as we only need values from the current row and the row above to compute the current cell.

1. **Empty Matrix**: If the input matrix is empty, the function should return 0, which we handle at the beginning of our function. 
2. **Single Element Matrix**: If the matrix contains only one element, the maximum path sum is that element itself.
3. **All Negative Values**: If the matrix contains negative values, the algorithm should still correctly compute the maximum path sum, as it will select the least negative path. 
4. **Single Row or Column**: The algorithm should handle cases where the matrix is either a single row or a single column, as it will still compute the sums correctly along that path.

Dynamic Programming on matrix

Palo Alto Networks

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

Palo Alto Networks 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