Is Minimum Obstacle Removal to Reach Corner easy or hard?

The problem is classified as Hard on LeetCode because it requires recognizing a shortest path formulation and applying an optimized graph technique. Understanding Dijkstra or 0-1 BFS is necessary to reach the optimal solution.

Minimum Obstacle Removal to Reach Corner Python/Java solution

Implement the solution using either a priority queue (heapq in Python or PriorityQueue in Java) or a deque for 0-1 BFS. The algorithm tracks the minimum obstacles removed while exploring four directions in the grid. Both implementations run in O(m*n log(m*n)) with a heap or O(m*n) with a deque.

How to solve Minimum Obstacle Removal to Reach Corner in O(n)?

Treat the grid as a graph and apply 0-1 BFS. Use a deque where moving to a free cell (0) is pushed to the front and moving through an obstacle (1) is pushed to the back. Maintain a distance matrix tracking the minimum obstacles removed to reach each cell. This processes each cell once, giving O(m*n) time.

What is the best approach for Minimum Obstacle Removal to Reach Corner?

The optimal approach is 0-1 BFS using a deque. Since moving into a free cell costs 0 and removing an obstacle costs 1, edges have only two weights. Using a deque lets you process zero-cost moves from the front and cost-1 moves from the back, achieving O(m*n) time with O(m*n) space.

Is Minimum Obstacle Removal to Reach Corner asked at Google/Amazon/Meta?

Grid shortest path problems with weighted edges are commonly asked by companies like Google, Amazon, and Meta. Variants involving BFS, Dijkstra, or 0-1 BFS appear frequently in technical interviews because they test graph modeling and algorithm optimization.

What data structure is used in Minimum Obstacle Removal to Reach Corner?

The problem typically uses a priority queue (min-heap) for the Dijkstra-style approach or a deque for the optimized 0-1 BFS solution. Both approaches also maintain a distance matrix to track the minimum number of obstacles removed for each grid cell.

What is the time complexity of Minimum Obstacle Removal to Reach Corner?

The priority queue (Dijkstra-like) solution runs in O(m*n log(m*n)) time because each grid cell may be pushed into a heap. Using the optimized 0-1 BFS approach reduces this to O(m*n) since each cell is processed with constant-time deque operations.

Description Hints 2 Solution Video 24:52

2290. Minimum Obstacle Removal to Reach Corner

Hard71.1% acceptance2 companies

You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:

0 represents an empty cell,
1 represents 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 to remove so you can move from the upper left corner (0, 0) to the lower 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.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
2 <= m * n <= 10⁵
grid[i][j] is either 0 or 1.
grid[0][0] == grid[m - 1][n - 1] == 0

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Model the grid as a graph where cells are nodes and edges are between adjacent cells. Edges to cells with obstacles have a cost of 1 and all other edges have a cost of 0.

Hint 2

Could you use 0-1 Breadth-First Search or Dijkstra’s algorithm?

24:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution