How should I practice Shortest Grid Path with Obstacle Elimination?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Shortest Grid Path with Obstacle Elimination associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Shortest Grid Path with Obstacle Elimination

Google● HardINTERNONSITE INTERVIEW

Learn

Problem statement

You are given an m x n binary grid. A value of 0 is an open cell, and a value of 1 is an obstacle.

Start at the top-left cell (0, 0). In one step, you may move one cell up, down, left, or right while remaining inside the grid. You may eliminate at most k obstacles by entering their cells.

Return the minimum number of steps needed to reach the bottom-right cell (m - 1, n - 1). Return -1 when no valid path exists.

Function

shortestPathWithObstacleEliminations(grid: int[][], k: int) → int

Examples

Example 1

grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]k = 1return = 6

A shortest route uses six steps and eliminates one obstacle.

Example 2

grid = [[0,1,1],[1,1,1],[1,0,0]]k = 1return = -1

Every route to the destination enters more than one obstacle, so the elimination budget is insufficient.

Example 3

grid = [[0]]k = 0return = 0

The start is already the destination, so no step is needed.

Constraints

1 <= m, n <= 40
grid[i][j] is 0 or 1.
grid[0][0] = grid[m - 1][n - 1] = 0
0 <= k <= m * n