LeetCode Problem 2290

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path

Solution

LeetCode 2290, Minimum Obstacle Removal to Reach Corner

Problem Understanding

This problem gives us a 2D grid where every cell is either empty or blocked by an obstacle. A value of 0 means we can move through the cell freely, while a value of 1 means the cell contains an obstacle that can be removed.

We start at the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1). From any cell, we may move in four directions:

• up
• down
• left
• right

The important detail is that entering a cell with value 1 costs one obstacle removal. Entering a cell with value 0 costs nothing.

The goal is not to minimize the number of steps. Instead, we must minimize the total number of obstacles removed along the path.

This is fundamentally a shortest path problem on a graph:

• every cell is a node

• moving to a neighboring cell is an edge

• the edge weight is:

• 0 if the neighbor is empty

• 1 if the neighbor is an obstacle

The constraints are very important:

• m * n <= 10^5
• the grid can therefore be very large
• any exponential or repeated exhaustive search will time out

The problem guarantees:

• the start cell is empty
• the destination cell is empty
• grid values are only 0 or 1

These guarantees simplify the implementation because we never need to remove the starting or ending cell.

Several edge cases are important:

• a grid where no obstacle removals are needed
• a grid where almost every move requires removing obstacles
• very narrow grids such as 1 x n or m x 1
• multiple different paths with the same removal count
• cases where the shortest geometric path is not the cheapest obstacle path

A naive BFS that minimizes steps instead of removals would fail because fewer moves does not necessarily mean fewer obstacles removed.

Approaches

Brute Force Approach

A brute force solution would explore every possible path from the start to the destination and count how many obstacles each path removes.

One way to think about this is using DFS with backtracking:

• recursively move in all four directions
• maintain the number of removed obstacles
• track visited cells to avoid cycles
• update the minimum answer whenever the destination is reached

This approach is correct because it eventually explores all valid paths and therefore cannot miss the optimal one.

However, it is computationally infeasible. The number of possible paths grows exponentially with grid size. Even moderate grids would produce an enormous search space.

Because the grid may contain up to 100000 cells, brute force exploration is completely impractical.

Optimal Approach, 0-1 BFS

The key observation is that edge weights are only 0 or 1.

That means this problem is a perfect fit for 0-1 BFS, which is a specialized shortest path algorithm for graphs whose edge weights are restricted to 0 and 1.

The idea is:

• moving into an empty cell costs 0
• moving into an obstacle costs 1

We use a deque instead of a normal queue:

• if moving to a neighbor costs 0, push it to the front
• if moving to a neighbor costs 1, push it to the back

This ordering guarantees that cells with smaller removal cost are processed first, similar to Dijkstra's algorithm but more efficient for binary weights.

The algorithm maintains the minimum obstacle removals needed to reach every cell.

Because each node and edge is processed efficiently, the solution runs in linear time relative to the grid size.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^(m*n))	O(m*n)	Explores all possible paths recursively
Optimal, 0-1 BFS	O(m*n)	O(m*n)	Uses deque-based shortest path for binary edge weights

Algorithm Walkthrough

1. Create a distance matrix called dist.

dist[r][c] stores the minimum number of obstacles removed to reach cell (r, c).

Initialize all values to infinity except the start cell:

dist[0][0] = 0

2. Create a deque for BFS processing.

The deque allows efficient insertion at both ends.

Start by inserting the top-left cell:

deque = [(0, 0)]

3. Define the four movement directions.

We may move:

• up
• down
• left
• right

4. Repeatedly process cells from the front of the deque.

The front always contains the currently cheapest state because:

• zero-cost moves are inserted at the front
• one-cost moves are inserted at the back

5. For the current cell, examine all four neighbors.

For each valid neighbor:

• determine whether it is an obstacle
• compute the new removal cost

new_cost = current_cost + grid[nr][nc]

6. If the new cost improves the known distance for that neighbor, update it.

if new_cost < dist[nr][nc]:
    dist[nr][nc] = new_cost

7. Decide where to insert the neighbor into the deque.

• If the neighbor is empty (0), insert at the front.
• If the neighbor is an obstacle (1), insert at the back.

This preserves shortest-path ordering. 8. Continue until the deque becomes empty or the destination is reached. 9. Return the minimum removal count stored at the destination cell.

Why it works

0-1 BFS is effectively an optimized version of Dijkstra's algorithm for graphs with edge weights restricted to 0 and 1.

The deque ordering guarantees that whenever a node is processed, we already know the minimum possible obstacle removal cost for that node. Zero-cost transitions are prioritized immediately by pushing them to the front, while cost-one transitions are deferred by pushing them to the back.

Because every relaxation only improves distances and nodes are processed in nondecreasing cost order, the algorithm correctly computes the minimum obstacle removals needed to reach the destination.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        dist = [[float("inf")] * cols for _ in range(rows)]
        dist[0][0] = 0

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        dq = deque([(0, 0)])

        while dq:
            row, col = dq.popleft()

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if 0 <= nr < rows and 0 <= nc < cols:
                    new_cost = dist[row][col] + grid[nr][nc]

                    if new_cost < dist[nr][nc]:
                        dist[nr][nc] = new_cost

                        if grid[nr][nc] == 0:
                            dq.appendleft((nr, nc))
                        else:
                            dq.append((nr, nc))

        return dist[rows - 1][cols - 1]

The implementation begins by initializing the dimensions of the grid and creating the dist matrix. Every cell starts with an infinite cost because we have not discovered any path to those cells yet.

The starting position (0, 0) is assigned cost 0 because we begin there without removing anything.

The deque is the core data structure of 0-1 BFS. Unlike a normal queue, it supports insertion at both the front and back in constant time.

During traversal, every neighbor is evaluated:

• entering an empty cell adds zero cost
• entering an obstacle adds one cost

If a better path is found, the distance matrix is updated.

The crucial optimization is:

• zero-cost neighbors go to the front
• cost-one neighbors go to the back

This ordering ensures that lower-cost states are always processed first.

Finally, the algorithm returns the minimum cost stored at the bottom-right cell.

Go Solution

package main

import "container/list"

func minimumObstacles(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	const INF = int(1e9)

	dist := make([][]int, rows)
	for i := 0; i < rows; i++ {
		dist[i] = make([]int, cols)
		for j := 0; j < cols; j++ {
			dist[i][j] = INF
		}
	}

	dist[0][0] = 0

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	deque := list.New()
	deque.PushFront([2]int{0, 0})

	for deque.Len() > 0 {
		front := deque.Front()
		deque.Remove(front)

		cell := front.Value.([2]int)
		row, col := cell[0], cell[1]

		for _, dir := range directions {
			nr := row + dir[0]
			nc := col + dir[1]

			if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
				newCost := dist[row][col] + grid[nr][nc]

				if newCost < dist[nr][nc] {
					dist[nr][nc] = newCost

					if grid[nr][nc] == 0 {
						deque.PushFront([2]int{nr, nc})
					} else {
						deque.PushBack([2]int{nr, nc})
					}
				}
			}
		}
	}

	return dist[rows-1][cols-1]
}

The Go implementation closely mirrors the Python solution.

Instead of Python's built-in deque, Go uses container/list to implement a double-ended queue.

The distance matrix is initialized manually because Go does not provide a built-in infinity value for integers. A large constant INF is used instead.

Cells are represented using fixed-size arrays [2]int, which store row and column coordinates efficiently.

Since Go slices are reference types, the grid itself is passed efficiently without copying.

Worked Examples

Example 1

Input:

grid = [
  [0,1,1],
  [1,1,0],
  [1,1,0]
]

Initial state:

Cell	Distance
(0,0)	0
all others	inf

Deque:

[(0,0)]

Process (0,0):

Neighbor	Cell Value	New Cost	Action
(1,0)	1	1	push back
(0,1)	1	1	push back

Deque becomes:

[(1,0), (0,1)]

Process (1,0):

Neighbor	Cell Value	New Cost
(2,0)	1	2
(1,1)	1	2

Deque:

[(0,1), (2,0), (1,1)]

Process (0,1):

Neighbor	Cell Value	New Cost
(0,2)	1	2

Eventually the algorithm reaches (2,2) with total cost 2.

Answer:

2

Example 2

Input:

grid = [
  [0,1,0,0,0],
  [0,1,0,1,0],
  [0,0,0,1,0]
]

Initial deque:

[(0,0)]

Process (0,0):

Neighbor	Cost
(1,0)	0
(0,1)	1

Because (1,0) has zero additional cost, it is pushed to the front.

Deque:

[(1,0), (0,1)]

The algorithm keeps prioritizing zero-cost paths.

A full zero-obstacle route exists:

(0,0)
→ (1,0)
→ (2,0)
→ (2,1)
→ (2,2)
→ (1,2)
→ (0,2)
→ (0,3)
→ (0,4)
→ (1,4)
→ (2,4)

No obstacle removals are needed.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m*n)	Each cell is processed efficiently through 0-1 BFS
Space	O(m*n)	Distance matrix and deque storage

The grid contains m * n cells. Each cell has at most four edges, and every edge relaxation occurs efficiently through deque operations.

Unlike standard Dijkstra's algorithm, which would require a priority queue and produce O(E log V) complexity, 0-1 BFS exploits the restricted edge weights to achieve linear complexity.

The distance matrix requires one value per cell, giving O(m*n) auxiliary space.

Test Cases

from typing import List

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        from collections import deque

        rows = len(grid)
        cols = len(grid[0])

        dist = [[float("inf")] * cols for _ in range(rows)]
        dist[0][0] = 0

        dq = deque([(0, 0)])

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while dq:
            r, c = dq.popleft()

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if 0 <= nr < rows and 0 <= nc < cols:
                    new_cost = dist[r][c] + grid[nr][nc]

                    if new_cost < dist[nr][nc]:
                        dist[nr][nc] = new_cost

                        if grid[nr][nc] == 0:
                            dq.appendleft((nr, nc))
                        else:
                            dq.append((nr, nc))

        return dist[rows - 1][cols - 1]

solution = Solution()

assert solution.minimumObstacles(
    [[0,1,1],[1,1,0],[1,1,0]]
) == 2  # example with required removals

assert solution.minimumObstacles(
    [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
) == 0  # example with zero removals

assert solution.minimumObstacles(
    [[0,0],[0,0]]
) == 0  # all empty cells

assert solution.minimumObstacles(
    [[0,1],[1,0]]
) == 1  # must remove exactly one obstacle

assert solution.minimumObstacles(
    [[0,1,1,1,0]]
) == 3  # single row grid

assert solution.minimumObstacles(
    [[0],[1],[1],[0]]
) == 2  # single column grid

assert solution.minimumObstacles(
    [[0,1,0],[0,1,0],[0,0,0]]
) == 0  # longer path cheaper than direct path

assert solution.minimumObstacles(
    [[0,1,1],[1,1,1],[1,1,0]]
) == 3  # dense obstacle grid

assert solution.minimumObstacles(
    [[0,0,1],[1,0,1],[1,0,0]]
) == 0  # winding zero-cost path exists

Test	Why
[[0,1,1],[1,1,0],[1,1,0]]	Validates standard obstacle removal case
[[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]	Confirms zero-cost path handling
[[0,0],[0,0]]	Tests completely empty grid
[[0,1],[1,0]]	Tests minimum nonzero answer
[[0,1,1,1,0]]	Tests single-row traversal
[[0],[1],[1],[0]]	Tests single-column traversal
[[0,1,0],[0,1,0],[0,0,0]]	Ensures algorithm prioritizes lower cost over shorter path
[[0,1,1],[1,1,1],[1,1,0]]	Tests heavy obstacle density
[[0,0,1],[1,0,1],[1,0,0]]	Tests winding optimal path

Edge Cases

One important edge case is a grid where no obstacle removals are required. A naive implementation might still explore expensive paths unnecessarily or incorrectly count removals. The 0-1 BFS solution handles this naturally because zero-cost moves are always prioritized by inserting them at the front of the deque.

Another important case is a very narrow grid, such as a single row or single column. In these scenarios there is effectively only one possible route. Some implementations accidentally assume both dimensions are larger than one or mishandle boundary checks. The solution safely validates all neighbor coordinates before processing them.

A third critical edge case occurs when the shortest path in terms of movement count is not the cheapest path in terms of obstacle removals. Standard BFS would fail here because BFS minimizes steps, not weighted cost. The 0-1 BFS algorithm correctly prioritizes states based on obstacle count, ensuring the globally optimal solution is found.

A final important case is a grid filled almost entirely with obstacles. In these situations many paths may repeatedly revisit cells with better costs. The distance matrix prevents unnecessary reprocessing because updates only occur when a strictly smaller obstacle count is discovered.