Minimum Obstacle Removal to Reach Corner

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 empty cell and 1 is an obstacle you may remove. You start at the top-left cell (0, 0) and move up, down, left, or right through empty cells. Return the **minimum number of obstacles** you must remove so that you can walk from (0, 0) to the bottom-right cell (m - 1, n - 1). Path length does not matter, only the number of removed obstacles. The start and target cells are always empty.

Examples

Input: grid = [[0,1,0,0],[0,1,1,0],[1,1,0,0]]
Output: 1
Remove the obstacle at `(0,1)` and walk along the top row, then down the last column.
Input: grid = [[0,0],[0,0]]
Output: 0
The grid is already open.
Input: grid = [[0,1,1],[1,1,1],[1,1,0]]
Output: 3
Every route passes through at least three interior cells, all of which are obstacles.

Constraints

  • `m == grid.length`, `n == grid[i].length`
  • `1 <= m, n <= 10^5` and `2 <= m * n <= 10^5`
  • `grid[i][j]` is `0` or `1`
  • `grid[0][0] == grid[m-1][n-1] == 0`

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