Abstract / Summary

Find the shortest path in a grid with obstacles by removing some obstacles to reach the target cell.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (600k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the shortest-path-with-obstacle-removal problem on a rectangular grid. Starting from the top-left cell, it searches for the minimum number of steps required to reach the bottom-right cell while being allowed to eliminate up to k obstacles (cells with value 1). The algorithm employs a best-first search driven by a priority queue, ensuring that states with fewer steps are expanded first. A memoization map records the smallest number of obstacles removed when a particular cell is visited, preventing redundant work.

Initialization

The function begins by extracting the grid dimensions and defining a compact representation of the four orthogonal moves.

height = len(grid)
width  = len(grid[0])
deltas = (0, +1, 0, -1, 0)          # compressed deltas for neighbor iteration
todo   = [[0, 0, 0, 0]]            # priority queue: steps, removed, x, y
seen   = {}                        # maps (x, y) → minimum removed encountered

The priority queue todo is seeded with the start state (zero steps, zero removals, at coordinate (0, 0)). The seen dictionary will later store the best removal count for each visited cell.

Main Loop

The core of the algorithm is a loop that repeatedly extracts the state with the smallest step count from the priority queue.

while todo:
    steps, removed, x, y = heappop(todo)

The use of heappop guarantees that states are processed in non-decreasing order of steps. This ordering is crucial for guaranteeing that the first time the target cell is dequeued, the associated step count is optimal.

Termination Check

Immediately after popping a state, the algorithm checks whether the current coordinates correspond to the destination cell.

if x == width - 1 and y == height - 1:
    return steps

If the destination is reached, the function returns the accumulated step count, which is the length of the shortest feasible path.

Pruning Redundant States

Before expanding a state, the algorithm consults the seen map to determine whether a better (i.e., fewer removals) path to the same cell has already been recorded.

best = seen.get((x, y), +inf)
if removed >= best:
    continue
seen[(x, y)] = removed

If the current state has removed at least as many obstacles as a previously recorded state for the same cell, it is discarded. This pruning eliminates paths that are strictly worse in terms of obstacle consumption, even if they might have the same step count.

Neighbor Exploration

The algorithm iterates over the four orthogonal neighbors using the compressed deltas tuple. For each neighbor, it verifies that the coordinates stay within grid bounds.

for dx, dy in zip(deltas, deltas[1:]):
    nx = x + dx
    ny = y + dy
    if 0 <= nx < width and 0 <= ny < height:
        ...

Inside the bounds check, the cell type determines the next action. If the neighbor is an obstacle (grid[ny][nx] == 1), the algorithm may traverse it only when the current removal count is below the allowed limit k. In that case, it pushes a new state with an incremented removal count.

if grid[ny][nx] == 1:
    if removed < k:
        heappush(todo, (steps + 1, removed + 1, nx, ny))

If the neighbor is free (grid[ny][nx] == 0), the algorithm pushes a new state without changing the removal count.

else:
    heappush(todo, (steps + 1, removed, nx, ny))

Both pushes preserve the step count increment, reflecting the cost of moving to an adjacent cell.

Edge Cases Handled

The implementation gracefully handles several edge conditions:

• Zero-size grid is implicitly avoided because the function assumes at least one row and one column; the initial dimensions are derived directly from the input list.
• Start equals target (a 1×1 grid) triggers the termination check on the first iteration, returning zero steps without entering neighbor expansion.
• All cells are obstacles: the algorithm will only succeed if k is at least the Manhattan distance from start to finish; otherwise, the priority queue empties and the function returns -1.
• Excessive obstacle budget: when k exceeds the number of obstacles on any possible path, the algorithm still respects the removal limit but does not waste it, because the pruning logic only cares about the count of removals, not the remaining budget.
• Multiple optimal paths: the priority queue ensures that the first discovered target state corresponds to the minimal step count, regardless of how many distinct optimal routes exist.

Performance Optimizations

Several design choices contribute to efficient execution:

• Best-first ordering via a heap ensures that the search expands states in order of increasing steps, which reduces the number of explored states compared to a naïve breadth-first search that would need to track all frontier layers explicitly.
• State pruning with seen eliminates any state that does not improve the removal count for a given cell. This dramatically cuts down the branching factor, especially in dense obstacle configurations where many paths converge on the same coordinates.
• Compressed neighbor deltas stored in a single tuple avoid constructing separate lists or tuples for each direction, reducing allocation overhead during neighbor iteration.
• In-place tuple unpacking when popping from the heap (steps, removed, x, y = heappop(todo)) avoids additional indexing operations.
• Early exit on reaching the target prevents unnecessary processing of remaining queue entries once the optimal solution is found.

The combination of a priority queue, aggressive pruning, and minimal per-iteration overhead yields a solution that scales well with grid size and obstacle density while respecting the removal budget constraint.

Imagine a tiny robot standing at the top left corner of a big square playground filled with blocks. Some spots have walls, and other spots are empty. The robot wants to reach the opposite corner, but it only has a special laser to zap through a few walls.

The robot keeps a list of all the different paths it could take, always picking the one that has taken the fewest steps so far. It also keeps a notebook to write down how many walls it has zapped at every spot it visits. If the robot reaches a spot again but realizes it has already been there with a better plan, it ignores the new path because it wants the most efficient way to walk.

As the robot checks each spot, it looks in all four directions: up, down, left, and right. If the next spot is empty, the robot just walks there. If there is a wall blocking the way, the robot checks its laser charge. If there is still power left, it zaps the wall and moves forward. It keeps doing this over and over until it finally arrives at the finish line. If the robot tries every possible way and still cannot reach the end, it stops and realizes the destination is impossible to reach.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	Go		TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	halfrost					Go
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	vthwang				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality