Shortest Path in a Grid with Obstacles Elimination
Updated
Problem statement
You are given an m x n binary grid. A value of 0 is an empty cell and a value of 1 is an obstacle. Start at (0, 0) and move one cell up, down, left, or right.
Return the minimum number of moves needed to reach (m - 1, n - 1) when you may eliminate at most k obstacles. Return -1 when the destination is unreachable.
Function
shortestPath(grid: int[][], k: int) → intExamples
Example 1
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]k = 1return = 6A shortest route has six moves and eliminates one obstacle.
Example 2
grid = [[0,1,1],[1,1,1],[1,0,0]]k = 1return = -1Every route to the destination crosses more than one obstacle.
Constraints
1 <= m, n <= 401 <= m * ngrid[i][j]is0or1.grid[0][0] = grid[m - 1][n - 1] = 00 <= k <= m * n
More Bloomberg LP Phone Screen questions
- N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Fewest Coins CombinationPHONE SCREEN · Seen Nov 2026
- Recommend Films from Viewers Who Watched Everything You DidPHONE SCREEN · Seen Nov 2026
- Track New Values in Sorted OrderPHONE SCREEN · Seen Nov 2026
- Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
- Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Shortest Grid Path with Obstacle EliminationsAmazon · ONSITE INTERVIEW
- Shortest Grid Path with Obstacle EliminationGoogle · ONSITE INTERVIEWGoogle interview questions
- Shortest Distance from All BuildingsWaymo · PHONE SCREENWaymo interview questions
- Shortest Path in a Grid with Obstacles EliminationMercor · PHONE SCREENMercor interview questions
- Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Shortest Path in a Blocked GridSpotify · PHONE SCREEN
- Shortest Path in a Binary MatrixMeta · PHONE SCREENMeta interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Shortest Path to Food with DirectionsZip · PHONE SCREENZip interview questions
- Safest Shortest Path Through a GridSnowflake · OASnowflake interview questions