Frontend School

Grid Path with Teleportation

DSA
hard

Grid Path with Teleportation

Hard
Dynamic Programming
2D DP
Grid

Overview

In a futuristic logistics network, you control an automated delivery drone navigating a complex grid-based city. Each cell in the city grid contains a specific resource value, which can be positive, negative, or zero. Your mission is to pilot the drone from the top-left corner (0, 0) to the bottom-right corner (R-1, C-1), collecting as much total value as possible. To enhance efficiency, the drone is equipped with a unique, single-use teleportation module. This problem challenges your ability to optimize pathfinding under a special constraint, a common scenario in resource management and route optimization systems.

What you need to do / Task

Implement the function maxGridPathValue that calculates the maximum possible total value the drone can collect while traversing the grid, considering the option to use a single teleport.

Input & output

Input:

  • grid: A 2D array of integers (number[][]) representing the city grid. grid[r][c] is the value at cell (r, c). You can only move right (r, c) -> (r, c+1) or down (r, c) -> (r+1, c).
  • teleportCost: A non-negative integer (number) representing the cost incurred if the teleportation module is used. This cost is subtracted from the total collected value.

Special Rule for Teleportation:

  • You can use the teleportation module at most once during your journey.
  • If you choose to teleport from cell (r1, c1) to cell (r2, c2), you must satisfy the conditions r2 >= r1 and c2 >= c1. This means you can only teleport to a cell that is 'ahead' or 'to the right' of your current position.
  • The teleportation itself adds grid[r2][c2] to your path sum and subtracts teleportCost. The value of grid[r1][c1] is also included in the path sum (as it's part of the path before teleporting).
  • After teleporting, you continue your journey from (r2, c2) to (R-1, C-1) using only right or down moves.

Output:

  • A single integer (number) representing the maximum total value collected.

Clarifications

  • The grid dimensions R (number of rows) and C (number of columns) will be at least 1.
  • Cell values in grid can be positive, negative, or zero.
  • The teleportCost is always non-negative. If teleportCost is very high, it might be optimal not to use the teleport.
  • You must always start at (0, 0) and end at (R-1, C-1). The values of both start and end cells are included in the path sum.

Examples

1

Example 1

Input:

grid = [[10, 5], [2, 12]], teleportCost = 3

Output:

36

Note:

Grid: [ [10, 5], [2, 12] ], Teleport Cost: 3

Path without teleport: (0,0) -> (0,1) -> (1,1) = 10 + 5 + 12 = 27 (0,0) -> (1,0) -> (1,1) = 10 + 2 + 12 = 24 Max without teleport = 27.

Path with teleport: Consider a path: (0,0) [value 10] -> (0,1) [value 5]. The sum collected without teleport up to (0,1) is 15. Now, if we teleport from (0,1) to (1,1): We add grid[1][1] (which is 12) and subtract teleportCost (which is 3). Total value for this path: 15 + 12 - 3 = 24.

Alternatively, consider teleporting directly from (0,0) to (1,1). The value collected up to (0,0) is grid[0][0] = 10. Teleport to (1,1) (value 12), cost 3. Total value: 10 + 12 - 3 = 19.

The optimal path with teleportation is derived from the maximum dp[r][c][0] value (path sum before teleporting) plus the current cell's value minus teleportCost, or by extending an already teleported path. The maximum value for dp[1][1][1] (max value to reach (1,1) having used teleport) is 36. This comes from teleporting to (1,1) from a prior cell that accumulated the maximum possible value without teleport up to that point (which is 27 at (1,1) itself, or earlier cells that contribute to this prefix max). So, 27 (max path sum without teleport up to any cell (pr,pc) with pr<=1, pc<=1) + grid[1][1] (12) - teleportCost (3) = 36.

Comparing 27 (no teleport) and 36 (with teleport), the maximum is 36.

2

Example 2

Input:

grid = [[1, 100, 1], [1, 1, 1]], teleportCost = 10

Output:

103

Note:

Grid: [ [1, 100, 1], [1, 1, 1] ], Teleport Cost: 10

Path without teleport: (0,0)->(0,1)->(0,2)->(1,2) = 1 + 100 + 1 + 1 = 103. (0,0)->(1,0)->(1,1)->(1,2) = 1 + 1 + 1 + 1 = 4. Max without teleport = 103.

Path with teleport: Consider teleporting from (0,0) to (0,1). Path (0,0) sum is 1. Teleport to (0,1), cost 10. Value at (0,1) is 100. Sum: 1 + 100 - 10 = 91. From (0,1), continue to (0,2) (value 1), then (1,2) (value 1). Total: 91 + 1 + 1 = 93.

Consider teleporting from (0,0) to (1,2). Path (0,0) sum is 1. Teleport to (1,2), cost 10. Value at (1,2) is 1. Sum: 1 + 1 - 10 = -8. This is worse than 103.

It turns out the optimal solution is to not use the teleport, yielding 103.

3

Example 3

Input:

grid = [[-5, -10], [-20, -1]], teleportCost = 0

Output:

-6

Note:

Grid: [ [-5, -10], [-20, -1] ], Teleport Cost: 0

Path without teleport: (0,0)->(0,1)->(1,1) = -5 + (-10) + (-1) = -16. (0,0)->(1,0)->(1,1) = -5 + (-20) + (-1) = -26. Max without teleport = -16.

Path with teleport: Since teleportCost is 0, we can teleport freely to maximize value. The maximum value to reach any cell (r,c) without teleport, plus grid[r][c] (if it's the teleport destination) is relevant.

One optimal path involves teleporting from (0,0) to (1,1). Value at (0,0) is -5. Teleport to (1,1), value -1, cost 0. Total: -5 + (-1) - 0 = -6. This is better than -16 or -26.

Final result is -6.

Constraints

Constraints & assumptions

  • 1 <= R, C <= 500 (where R is the number of rows, C is the number of columns)
  • -1000 <= grid[r][c] <= 1000
  • 0 <= teleportCost <= 10^9
  • The final result can be a negative number.

Out of scope

  • Path reconstruction (only the maximum value is required).
  • Multiple teleportations or teleportations with different rules (e.g., specific range, different costs).
  • Movements other than right or down.

What interviewers evaluate

  • Correctness: Does the solution correctly calculate the maximum value for all valid inputs, including edge cases?
  • Efficiency: Is the solution's time and space complexity optimal for the given constraints?
  • Dynamic Programming Application: Does the solution effectively leverage 2D (or 3D) Dynamic Programming to solve the problem?
  • Code Clarity & Structure: Is the code well-organized, readable, and appropriately commented?

Loading editor...