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. Topics: Array, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path, 0-1 BFS, Dijkstra’s Algorithm. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

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

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.

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, full suite in test_solution.py:

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.