Abstract / Summary

Given a grid with walls and gates, find the shortest path from a starting cell to any gate.

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 37% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Hash Table

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 presented implementation determines whether a path exists between two points on a massive 1-million-by-1-million grid while a small set of cells (at most 200) are blocked. The algorithm relies on a depth-first search that is deliberately limited: if the search can move more than 200 steps away from its start point, it concludes that the blocked cells cannot form a complete enclosure. The same limited search is performed from the source toward the target and from the target back toward the source; both must succeed for the overall result to be True.

Core Logic

The first significant operation converts the list of blocked coordinates into a hash set for O(1) membership tests.

blocks = set((x, y) for x, y in blocked)

The heart of the solution is the nested deeper function, which receives a start coordinate (sx, sy) and a destination (tx, ty). It uses an explicit stack todo to explore reachable cells and a seen set to avoid revisiting positions.

def deeper(sx, sy, tx, ty):
    todo = [(sx, sy)]
    seen = set()
    while todo:
        next = todo.pop()
        if next in seen:
            continue
        seen.add(next)

        if next in blocks:
            continue

        x, y = next
        if x == tx and y == ty:
            return True
        ...

Inside the loop the algorithm checks whether the current cell matches the target; if so, it returns True. The next crucial test measures the Manhattan distance from the start. If the cumulative distance exceeds 200, the function assumes that the search has escaped any possible enclosure and returns True.

dx = abs(x - sx)
dy = abs(y - sy)
if dx + dy > 200:
    return True

If the search has not yet escaped, the algorithm adds the four orthogonal neighbours that stay within the grid bounds to the stack.

if x > 0:
    todo.append((x - 1, y))
if y > 0:
    todo.append((x, y - 1))
if x < 999_999:
    todo.append((x + 1, y))
if y < 999_999:
    todo.append((x, y + 1))

When the stack is exhausted without reaching the target or exceeding the distance threshold, the function returns False, indicating that the start is trapped by the blocked cells.

The outer method extracts the source and target coordinates and invokes deeper twice, swapping the roles of source and target. Both calls must succeed for the final answer to be True.

sx, sy = source
tx, ty = target
return deeper(sx, sy, tx, ty) and deeper(tx, ty, sx, sy)

Edge Cases Handled

The algorithm explicitly handles the situation where the start or target lies on the grid border. The boundary checks (x > 0, y > 0, x < 999_999, y < 999_999) prevent attempts to move outside the defined coordinate range, thereby avoiding invalid positions.

If the source and target are the same cell, the first distance check is bypassed because the equality test x == tx and y == ty succeeds immediately, returning True.

When the blocked list is empty, the set blocks is empty, so the search proceeds unimpeded. The distance threshold of 200 is never reached before the target is found, leading to a successful result.

If the blocked cells form a partial wall that does not completely enclose the start, the distance check will eventually exceed 200 as the search walks around the opening, causing the function to return True. Conversely, a full enclosure of fewer than 200 cells will keep the search confined within the distance limit, and the function will return False.

Performance Optimizations

The conversion of blocked into a hash set eliminates linear scans for each neighbor check, reducing the cost of “is this cell blocked?” to constant time.

The use of a stack (todo) implements an iterative depth-first search, avoiding the overhead of recursive calls and the associated call-stack limits on large grids.

The early exit conditions-reaching the target or surpassing the 200-step Manhattan distance-prune the search space dramatically. In the worst case, the algorithm explores at most the region that could be surrounded by 200 blocked cells, which is bounded and independent of the overall grid size.

By performing the search from both source to target and target to source, the algorithm guarantees correctness even when one side is enclosed while the other is not. Each direction benefits from the same bounded exploration, keeping the total work limited.

The explicit seen set prevents revisiting cells, ensuring each reachable coordinate is processed at most once per direction. This eliminates redundant work and keeps the runtime proportional to the size of the reachable region rather than the total number of possible grid cells.

Overall, the combination of hash-based blocked lookup, bounded depth-first traversal, early termination on distance, and bidirectional checks yields a solution that scales efficiently despite the enormous theoretical grid size.

Imagine a giant, empty playground that is so enormous that you could walk forever and never find an edge. In this playground, there are some special spots marked as blocked, kind of like puddles you are not allowed to step in. The goal is to see if a friend can start at one place and travel to another place without getting stuck behind a circle of these blocked spots.

To solve this, the code acts like a tiny explorer. It starts at the beginning spot and looks in every direction to see if it can reach the destination. Because the playground is so big, the explorer keeps track of all the steps it takes. If the explorer can travel far enough away from the start, it means there is no way for those blocked spots to completely surround it, so it is definitely possible to keep moving forward.

The code does this twice, once starting from where you begin and once starting from where you want to go. By checking both ways, it makes sure that neither player gets trapped in a little corner. As long as the path remains open, the explorer knows it will eventually find the way to the other side.

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	Rust	TS
	LeetcodeHelp	C++		Python	Java
	MemoryLimitExceeded	C++		Python
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
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