Maximize Cashback Path in Grid
At PhonePe, we are constantly innovating ways for users to earn rewards and cashback. Imagine a new gamified feature where users navigate a grid-based map to collect cashback. Each cell on the map represents a potential transaction point with a specific cashback value. Some cells might be temporarily unavailable or blocked due to system maintenance or security reasons.
Your task is to help users find the most lucrative path through this grid to maximize their total collected cashback. This problem is crucial for designing engaging and rewarding user experiences while ensuring system constraints are respected.
Implement the function maxCashbackPath that calculates the maximum total cashback a user can collect by starting at the top-left corner (0, 0) and reaching the bottom-right corner (R-1, C-1) of a given grid. The user can only move right or down at each step.
Function Signature:
function maxCashbackPath(grid: number[][]): number {
// your code here
}
Parameters:
grid: A 2D array of integers (number[][]). grid[r][c] represents the cashback value at cell (r, c). A value of -1 indicates that the cell is blocked and cannot be entered.Return Value:
(0, 0) to (R-1, C-1), return -1.grid[r][c] is -1, that cell is impassable. You cannot move into it or through it.(0, 0) or the ending cell (R-1, C-1) is blocked (-1), no valid path exists.-1.Examples
Example 1
Input:
grid = [[1, 2, 3],[4, 5, 6]]
Output:
16
Note:
Path: (0,0) -> (1,0) -> (1,1) -> (1,2) with sum 1 + 4 + 5 + 6 = 16. Another path (0,0) -> (0,1) -> (0,2) -> (1,2) gives 1 + 2 + 3 + 6 = 12. The maximum is 16.
Example 2
Input:
grid = [[1, -1, 3],[4, 5, 6]]
Output:
16
Note:
Cell (0,1) is blocked. The only valid path to maximize cashback is (0,0) -> (1,0) -> (1,1) -> (1,2) with sum 1 + 4 + 5 + 6 = 16.
Example 3
Input:
grid = [[1, -1],[ -1, 2]]
Output:
-1
Note:
Both paths from (0,0) to (1,1) are blocked by cells (0,1) and (1,0). No valid path exists.
Example 4
Input:
grid = [[-1, 10],[10, 10]]
Output:
-1
Note:
The starting cell (0,0) is blocked, so no path is possible.
Constraints
1 <= R, C <= 200 (where R is the number of rows and C is the number of columns in the grid).0 <= grid[r][c] <= 1000 for non-blocked cells.grid[r][c] can be -1 for blocked cells.Loading editor...