Minimum Obstacle Removal to Reach Corner
01 · Problem
You are given an m x n binary grid. A cell containing 0 is empty and can be walked through; a cell containing 1 is an obstacle that must be removed before you can enter it.
Starting at the top-left cell (0, 0), you may move one step up, down, left or right to any cell inside the grid. Return the minimum number of obstacles you must remove so that you can reach the bottom-right cell (m - 1, n - 1).
The start and end cells are always empty, so the answer is always defined (it may be 0).
02 · Examples
grid = [[0,1,1],[1,1,0],[1,0,0]]
2
Go down twice to (2,0), removing the obstacles at (1,0) and (2,0), then walk right through empty cells to (2,2). At least two obstacles block every route.
grid = [[0,0,1,0],[1,0,1,0],[1,0,0,0]]
0
The path (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) -> (2,3) only uses empty cells, so nothing needs to be removed.
grid = [[0,1,0],[0,1,0],[0,1,0]]
1
Column 1 is a full wall, so at least one obstacle must go. Removing (0,1) and walking along the top row is enough.
03 · Constraints
- 01m == grid.length, n == grid[i].length
- 021 <= m, n <= 105 and 2 <= m * n <= 105
- 03grid[i][j] is either 0 or 1
- 04grid[0][0] == grid[m - 1][n - 1] == 0
04 · Optimal complexity
- Time
- O(m * n)
- Space
- O(m * n)
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.