> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Obstacle Removal to Reach Corner

> Tested Python solution for LeetCode 2290 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 2290, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph Theory](/catalog/topics/graph-theory), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Matrix](/catalog/topics/matrix), [Shortest Path](/catalog/topics/shortest-path), 0-1 BFS, Dijkstra's Algorithm. [View on LeetCode](https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2290   # by problem number
lcpy gen -s minimum_obstacle_removal_to_reach_corner   # by problem name
```

## Problem

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)`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png)

```
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](https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png)

```
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^5`
* `2 <= m * n <= 10^5`
* `grid[i][j]` is either `0` or `1`.
* `grid[0][0] == grid[m - 1][n - 1] == 0`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_obstacle_removal_to_reach_corner/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_obstacle_removal_to_reach_corner/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(m * n)
    # Space: O(m * n)
    def minimum_obstacles(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dist = [[-1] * cols for _ in range(rows)]
        dist[0][0] = 0
        dq: deque[tuple[int, int, int]] = deque([(0, 0, 0)])
        while dq:
            cost, r, c = dq.popleft()
            if cost > dist[r][c]:
                continue
            if r == rows - 1 and c == cols - 1:
                return cost
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols:
                    ncost = cost + grid[nr][nc]
                    if dist[nr][nc] == -1 or ncost < dist[nr][nc]:
                        dist[nr][nc] = ncost
                        if grid[nr][nc]:
                            dq.append((ncost, nr, nc))
                        else:
                            dq.appendleft((ncost, nr, nc))
        return dist[rows - 1][cols - 1]
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n) | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.