Shortest Path in a Grid with Obstacles Elimination
01 · Problem
You are given an m x n grid where 0 is an empty cell and 1 is an obstacle, and an integer k. In one step you may move up, down, left or right to a cell inside the grid.
You may walk through at most k obstacles in total (each obstacle cell you enter uses up one elimination). Return the minimum number of steps to go from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1), or -1 if it is impossible.
If the grid has a single cell, the answer is 0.
02 · Examples
grid = [[0,1,0],[0,1,0],[0,1,0]], k = 1
4
Column 1 is a solid wall, so one elimination is needed. Path (0,0) -> (0,1) [eliminate] -> (0,2) -> (1,2) -> (2,2) takes 4 steps, which equals the Manhattan distance.
grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
-1
Every route from the corner must pass through at least two obstacles, but only one elimination is allowed.
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
6
Walk right to (0,2), down to (2,2), eliminate the obstacle at (3,2) and step down to (4,2): 6 steps.
03 · Constraints
- 01m == grid.length, n == grid[i].length
- 021 <= m, n <= 40
- 031 <= k <= m * n
- 04grid[i][j] is 0 or 1
- 05grid[0][0] == grid[m - 1][n - 1] == 0
04 · Optimal complexity
- Time
- O(m * n * k)
- Space
- O(m * n * k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.