Shortest Path in a Grid with Obstacles Elimination

HardGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n grid where 0 is an open cell and 1 is an obstacle. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1). Each step moves you one cell up, down, left, or right, staying inside the grid. You may walk through **at most k** obstacle cells in total (think of it as demolishing them). Stepping onto an obstacle uses up one of your k eliminations; open cells are free. Return the **minimum number of steps** needed to reach the bottom-right cell, or -1 if it cannot be reached with at most k eliminations. The start and target cells are always open; if they are the same cell the answer is 0.

Examples

Input: grid = [[0,1,0,0],[0,1,1,0],[0,0,1,0]], k = 1
Output: 5
Go right through the obstacle at `(0,1)`, then along the top row and down the last column: 5 steps using one elimination. No path exists without eliminating something.
Input: grid = [[0,1,0,0],[0,1,1,0],[0,0,1,0]], k = 0
Output: -1
Without eliminations the start is sealed in by obstacles at `(0,1)`, `(1,1)`, `(2,2)`, and `(1,2)`, so the target is unreachable.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems