LeetCode Solutions Blog

Minimum Obstacle Removal to Reach Corner

Number: 2375

Difficulty: Hard

Paid? No

Problem Description

Given a 2D grid where 0 represents an empty cell and 1 represents an obstacle, find the minimum number of obstacles to remove to travel from the upper-left corner (0, 0) to the lower-right corner (m - 1, n - 1). Movement is allowed in four directions: up, down, left, and right. The start and destination cells are guaranteed to be 0 (empty).

Key Insights

The grid can be interpreted as a weighted graph where moving through an empty cell (0) has cost 0 and moving through an obstacle (1) has cost 1.
The goal is to find the path with the minimum total cost.
Use a 0-1 BFS or a modified Dijkstra's algorithm to efficiently process the grid.
0-1 BFS optimizes the traversal by using a deque: pushing 0-cost moves to the front and 1-cost moves to the back.

Space and Time Complexity

Time Complexity: O(m * n) since each cell is processed at most once. Space Complexity: O(m * n) for the deque and the visited/cost matrix.

Solution

We solve the problem by leveraging 0-1 BFS. The grid is modeled as a weighted graph where:

Moving to a neighbor cell with value 0 has no additional cost.
Moving to a neighbor cell with value 1 incurs a cost of 1 (obstacle removal).

A deque (double-ended queue) is used:

When moving to an empty cell (0), push the new position to the front of the deque.
When moving to an obstacle (1), push the new position to the back.

This ensures positions that cost 0 are prioritized, and we maintain an array or matrix to keep track of the minimum obstacles removed to reach each cell.

The algorithm terminates when the destination cell is dequeued with the minimum cost, or when all cells are processed.

Code Solutions

from collections import deque

def minimumObstacles(grid):
    # Number of rows and columns
    m, n = len(grid), len(grid[0])
    # Initialize deque with the starting position and initial cost 0
    dq = deque([(0, 0, 0)])  # (row, col, obstacles_removed)
    
    # Create a 2D list to track the minimum obstacles removed to reach each cell
    min_removed = [[float('inf')] * n for _ in range(m)]
    min_removed[0][0] = 0
    
    # Directions: up, down, left, right
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Process the deque BFS style using 0-1 BFS approach
    while dq:
        r, c, cost = dq.popleft()
        # If destination is reached, return the cost
        if r == m - 1 and c == n - 1:
            return cost
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check bounds
            if 0 <= nr < m and 0 <= nc < n:
                # Calculate new_cost: add 1 if there is an obstacle, else add 0
                new_cost = cost + grid[nr][nc]
                # Only proceed if this new_cost is better than any previously found
                if new_cost < min_removed[nr][nc]:
                    min_removed[nr][nc] = new_cost
                    # For cost 0, append left; for cost 1, append right
                    if grid[nr][nc] == 0:
                        dq.appendleft((nr, nc, new_cost))
                    else:
                        dq.append((nr, nc, new_cost))
    # If destination is unreachable, though the problem guarantees it is reachable.
    return -1

# Example usage:
grid_example = [[0, 1, 1], [1, 1, 0], [1, 1, 0]]
print(minimumObstacles(grid_example))