#2290
Minimum Obstacle Removal to Reach Corner
specialist · 985 · lc hard +32 · verified · 70.5% accepted · 1,661 likes · top 79%
Description
You are given a 0-indexed 2D integer array grid of size m x n where:
- 0 is an empty cell,
- 1 is a removable obstacle.
You can move up, down, left, or right through empty cells.
Return the minimum number of obstacles to remove in order to have a clear path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1).
Example 1:
Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.
Example 2:
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
Code
1
2
3