Frontend School

Optimal Path with Dynamic Jumps

DSA
hard

Optimal Path with Dynamic Jumps

Hard
Recursion
Dynamic Programming
Grid
Pathfinding

Overview

Browserstack's infrastructure manages vast grids of virtual machines and testing resources. Efficiently allocating and navigating these resources for optimal performance is crucial. This problem models a simplified scenario where you need to find the most valuable path through a grid, but with a unique twist: your movement capabilities (jump length) are dynamic and depend on the current cell's properties. Solving this requires careful recursive thinking and optimization.

What you need to do / Task

Implement a function maxPathSumWithDynamicJumps that calculates the maximum possible sum of values of cells visited along a path from the top-left cell (0, 0) to the bottom-right cell (M-1, N-1) in a given grid. You can only move right or down.

From any cell (r, c), you can make a "jump" of k steps either horizontally (to (r, c + k)) or vertically (to (r + k, c)). The value of k can be any integer from 1 up to jumpPower[r][c], where jumpPower[r][c] is a predefined maximum jump length specific to cell (r, c).

Your path must include both the starting cell (0, 0) and the ending cell (M-1, N-1).

Input & output

Function Signature:

function maxPathSumWithDynamicJumps(grid: number[][], jumpPower: number[][]): number

Parameters:

  • grid: A 2D array of numbers (number[][]) representing the values of each cell. grid[r][c] is the value of the cell at row r and column c.
  • jumpPower: A 2D array of numbers (number[][]) of the same dimensions as grid. jumpPower[r][c] indicates the maximum number of steps k you can jump from cell (r, c) in a single move (either right or down).

Returns:

  • number: The maximum possible sum of values of cells along an optimal path from (0,0) to (M-1, N-1). If no path exists, this problem guarantees a path always exists. The sum can be negative.

Clarifications

  • Start and End: The path must start at (0,0) and end at (M-1, N-1). Both cells contribute their values to the total sum.
  • Movement: You can only move right or down. Diagonal moves are not allowed.
  • Jump Length: From cell (r, c), you can jump k steps right (to (r, c+k)) or k steps down (to (r+k, c)), where 1 <= k <= jumpPower[r][c].
  • Negative Values: Cell values in grid can be negative, so the maximum path sum might also be negative.
  • Reachability: It is guaranteed that a valid path from (0,0) to (M-1, N-1) always exists under the given constraints.

Examples

1

Example 1

Input:

grid = [[1,10,-5],[2,1,-1],[4,2,3]], jumpPower = [[1,1,1],[1,1,1],[1,1,1]]

Output:

17

Note:

Grid: 1 10 -5 2 1 -1 4 2 3 Jump Power: All cells allow a maximum jump of 1.

Path: (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) Sum: 1 + 10 + 1 + 2 + 3 = 17.

2

Example 2

Input:

grid = [[10, -5, 1], [-1, 20, -2], [3, -10, 5]], jumpPower = [[2, 1, 1], [1, 2, 1], [1, 1, 0]]

Output:

32

Note:

Grid: 10 -5 1 -1 20 -2 3 -10 5 Jump Power: 2 1 1 1 2 1 1 1 0

Optimal Path: (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) From (0,0) [val 10, jumpP=2]: Jump 1 down to (1,0). From (1,0) [val -1, jumpP=1]: Jump 1 right to (1,1). From (1,1) [val 20, jumpP=2]: Jump 1 right to (1,2). From (1,2) [val -2, jumpP=1]: Jump 1 down to (2,2). Total Sum: 10 + (-1) + 20 + (-2) + 5 = 32.

3

Example 3

Input:

grid = [[10, 1, 5], [2, 100, 3], [4, 6, 7]], jumpPower = [[2, 1, 1], [1, 2, 1], [1, 1, 0]]

Output:

125

Note:

Grid: 10 1 5 2 100 3 4 6 7 Jump Power: 2 1 1 1 2 1 1 1 0

Optimal Path: (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2) From (0,0) [val 10, jumpP=2]: Jump 1 down to (1,0). From (1,0) [val 2, jumpP=1]: Jump 1 right to (1,1). From (1,1) [val 100, jumpP=2]: Jump 1 down to (2,1). From (2,1) [val 6, jumpP=1]: Jump 1 right to (2,2). Total Sum: 10 + 2 + 100 + 6 + 7 = 125.

Constraints

Constraints & assumptions

  • 1 <= M, N <= 50, where M is the number of rows and N is the number of columns in the grid.
  • grid and jumpPower will always have the same dimensions (M x N).
  • -100 <= grid[r][c] <= 100 for all r, c.
  • 0 <= jumpPower[r][c] <= max(M, N) for all r, c. A jumpPower of 0 means no moves are possible from that cell, effectively making it a dead end unless it's the target cell itself.
  • All inputs are valid and well-formed.

Out of scope

  • Input validation (e.g., checking if grid and jumpPower dimensions match).
  • Reconstructing the actual path; only the maximum sum is required.

What interviewers evaluate

  • Correctness of Recursive Logic: Ability to correctly define the recursive relationship, base cases, and state transitions for pathfinding with dynamic jumps.
  • Memoization/Dynamic Programming: Effective use of memoization to optimize the recursive solution and avoid redundant computations.
  • Edge Case Handling: Proper handling of boundary conditions, including jumps that go out of bounds or reaching the destination cell.
  • Time and Space Complexity: Accurate analysis of the solution's time and space requirements.
  • Code Clarity and Structure: Well-organized, readable, and maintainable code.

Loading editor...