2290. Minimum Obstacle Removal to Reach Corner

Minimum Obstacle Removal to Reach Corner (LeetCode 2290) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

How to solve Minimum Obstacle Removal to Reach Corner

Minimum Obstacle Removal to Reach Corner is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Work towards the solution in these steps:

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.
2. Could you use 0-1 Breadth-First Search or Dijkstra’s algorithm?

The reference solution runs in O(m * n) time and O(m * n) space.

The Minimum Obstacle Removal to Reach Corner solution and editorial walks through the full approach with reference code.

Problem statement

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 <= 105

- 2 <= m n <= 105

- grid[i][j] is either 0 or 1.

- grid[0][0] == grid[m - 1][n - 1] == 0

Topics and companies

Topics: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path.

How to practise Minimum Obstacle Removal to Reach Corner on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.

Open Minimum Obstacle Removal to Reach Corner in the code editor, or read the Minimum Obstacle Removal to Reach Corner editorial for a worked solution with its approach and complexity analysis.

Where Minimum Obstacle Removal to Reach Corner sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Dijkstra's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Minimum Obstacle Removal to Reach Corner

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Find the Safest Path in a Grid — Medium, same subpattern
• Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
• Minimum Weighted Subgraph With the Required Paths — Hard, same subpattern
• Network Delay Time — Medium, same subpattern
• Number of Ways to Arrive at Destination — Medium, same subpattern
• Path with Maximum Probability — Medium, same subpattern

Minimum Obstacle Removal to Reach Corner FAQ