DSA problem
Minimum Obstacle Removal to Reach Corner
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values: 0 representing an empty cell, and 1 representing an obstacle that may be removed. You can move up, down, left, or right from and to an empty cell. Return the minimum number of obstacles you need to remove so you can move from the upper-left corner (0, 0) to the lower-right corner (m - 1, n - 1).
This is a shortest-path problem on a graph whose edge weights are either 0 (moving onto an empty cell) or 1 (moving onto an obstacle, which must be removed). Standard BFS would be incorrect because the edges are no longer unit-weight; standard Dijkstra would work but adds a logarithmic factor unnecessarily.
The optimal approach is 0-1 BFS using a double-ended queue (deque). When we relax an edge of weight 0, we push the neighbour to the front of the deque; when we relax an edge of weight 1, we push it to the back. This ensures that the deque always has cells in non-decreasing order of distance, mimicking Dijkstra without a priority queue.
Maintain a dist matrix initialised to infinity, set dist[0][0] = 0, and process the deque until empty. When we relax grid[nr][nc] we compute newDist = dist[r][c] + grid[nr][nc] and only enqueue it if it improves the previously recorded distance. The answer is dist[m - 1][n - 1]. Time complexity is O(m * n) since each cell is settled once, and space is O(m * n) for the distance matrix and deque.
Examples
grid = [[0,1,1],[1,1,0],[1,1,0]]2grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]0grid = [[0,0,0],[0,1,0],[0,0,0]]0Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10^5
- 2 <= m * n <= 10^5
- grid[i][j] is either 0 or 1.
- grid[0][0] == grid[m - 1][n - 1] == 0
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.