Frontend School

Maximize Cashback Path in Grid

DSA
medium

Maximize Cashback Path in Grid

Medium
Dynamic Programming
2D DP
Grid

Overview

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.

What you need to do / Task

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.

Input & output

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:

  • An integer representing the maximum total cashback achievable. If no valid path exists from (0, 0) to (R-1, C-1), return -1.

Clarifications

  • Blocked cells: If grid[r][c] is -1, that cell is impassable. You cannot move into it or through it.
  • Start/End cells: If the starting cell (0, 0) or the ending cell (R-1, C-1) is blocked (-1), no valid path exists.
  • Cashback values: Cashback values (non-blocked cells) will be non-negative integers.
  • No path: If there's no way to reach the destination due to blocked cells, return -1.

Examples

1

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.

2

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.

3

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.

4

Example 4

Input:

grid = [[-1, 10],[10, 10]]

Output:

-1

Note:

The starting cell (0,0) is blocked, so no path is possible.

Constraints

Constraints & assumptions

  • 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.
  • The grid will always contain at least one row and one column.

What interviewers evaluate

  • Correct application of 2D dynamic programming principles.
  • Proper handling of base cases and state transitions, especially with blocked cells.
  • Optimal time and space complexity for the given constraints.
  • Robustness in handling edge cases like unreachable paths or blocked start/end points.

Loading editor...