LeetCode 1036 - Escape a Large Maze

The problem gives us a massive 1,000,000 x 1,000,000 grid. Each cell is identified by coordinates (x, y), and movement is allowed in four directions: up, down, left, and right. Some cells are blocked, meaning we cannot step onto them.

leetcodehardarrayhash-tabledepth-first-searchbreadth-first-search

LeetCode Problem 1036

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem gives us a massive 1,000,000 x 1,000,000 grid. Each cell is identified by coordinates (x, y), and movement is allowed in four directions: up, down, left, and right. Some cells are blocked, meaning we cannot step onto them.

We are given three inputs:

  • blocked, a list of blocked coordinates
  • source, the starting coordinate
  • target, the destination coordinate

The goal is to determine whether there exists any valid path from source to target without stepping outside the grid or onto blocked cells.

At first glance, this looks like a standard graph traversal problem where each cell is a node and adjacent cells are connected by edges. Normally, Breadth-First Search or Depth-First Search would solve this easily.

However, the constraints fundamentally change the problem:

  • The grid contains up to 10^12 cells
  • blocked.length <= 200

The grid is astronomically large, which makes traversing the entire space impossible. A naive BFS over the grid would never finish in time or memory.

The important observation is that although the grid is huge, the number of blocked cells is extremely small. With at most 200 blocked cells, the blocked region can only enclose a limited area.

Several edge cases are important:

  • The source may be completely trapped by blocked cells
  • The target may be completely trapped
  • There may be no blocked cells at all
  • The source and target may be extremely far apart
  • The blocked cells may form partial walls that look dangerous but do not actually enclose anything

The problem guarantees that neither source nor target is blocked, and that they are distinct coordinates.

Approaches

Brute Force Approach

The brute force idea is straightforward:

  • Start BFS from source
  • Explore all reachable cells
  • Return true if we eventually reach target
  • Return false if BFS exhausts all possibilities

This works because BFS explores every reachable state exactly once, guaranteeing correctness.

Unfortunately, this approach is completely infeasible.

The grid contains 10^12 cells. Even if the path is short, BFS may need to explore enormous portions of the grid. Memory usage alone would become impossible.

The key issue is that the search space is far too large.

Key Insight

The crucial observation is that there are only at most 200 blocked cells.

A small number of blocked cells cannot surround an arbitrarily large region. In fact, the maximum enclosed area is bounded.

If we can prove that a search escapes the potentially enclosed region around the source, then the source is not trapped. The same logic applies to the target.

This transforms the problem:

We do not need to search the entire grid.

We only need to determine whether either endpoint is enclosed by blocked cells.

For n blocked cells, the maximum enclosed area is approximately:

$\frac{n(n-1)}{2}$

With n <= 200, this value is at most 19,900.

Therefore:

  • If BFS expands beyond this limit, we know the start point is not enclosed
  • If both source and target are not enclosed, a path must exist between them in the open grid

This allows a bounded BFS that terminates quickly.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(10^12) O(10^12) Attempts to explore the massive grid directly
Optimal O(B²) O(B²) Uses the bounded enclosure property of blocked cells

Here, B = len(blocked).

Algorithm Walkthrough

Step 1: Convert blocked cells into a hash set

We store all blocked coordinates in a hash set for constant time lookup.

This is important because during BFS we constantly need to check whether a neighboring cell is blocked.

A tuple like (x, y) is used as the key.

Step 2: Compute the maximum possible enclosed area

If there are n blocked cells, the largest region they can fully surround is:

$\frac{n(n-1)}{2}$

This value becomes our BFS exploration limit.

If BFS visits more than this many cells, then the search has escaped any possible enclosure.

Step 3: Run bounded BFS from the source

We perform BFS starting at source.

For each position:

  1. Remove one cell from the queue
  2. Check its four neighbors
  3. Ignore neighbors that:
  • are outside the grid
  • are blocked
  • were already visited
  1. Add valid neighbors into the queue

The BFS stops early in two cases:

  • We reach the target directly
  • We visit more cells than the enclosure limit

If we exceed the limit, we know the source is not trapped.

Step 4: Run bounded BFS from the target

We repeat the same process starting from target.

This step is necessary because:

  • The source might not be enclosed
  • But the target still could be enclosed

Both endpoints must be capable of escaping their local region.

Step 5: Combine the results

The final answer is:

  • true if both searches succeed
  • false otherwise

A search succeeds if:

  • It reaches the other endpoint
  • Or it escapes the maximum enclosure boundary

Why it works

The correctness relies on a geometric property:

With at most 200 blocked cells, there is a strict upper bound on the area they can fully enclose.

If BFS expands beyond that bound, then the search must have escaped any possible trapped region.

Since the infinite open area outside enclosed regions is connected, if both source and target are not trapped, a path between them must exist.

Python Solution

from collections import deque
from typing import List, Set, Tuple

class Solution:
    def isEscapePossible(
        self,
        blocked: List[List[int]],
        source: List[int],
        target: List[int]
    ) -> bool:

        BLOCK_LIMIT = len(blocked) * (len(blocked) - 1) // 2
        GRID_SIZE = 10**6

        blocked_set: Set[Tuple[int, int]] = {
            (x, y) for x, y in blocked
        }

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

        def bfs(start: List[int], finish: List[int]) -> bool:
            queue = deque()
            queue.append((start[0], start[1]))

            visited = set()
            visited.add((start[0], start[1]))

            while queue and len(visited) <= BLOCK_LIMIT:
                x, y = queue.popleft()

                if [x, y] == finish:
                    return True

                for dx, dy in directions:
                    nx = x + dx
                    ny = y + dy

                    if not (0 <= nx < GRID_SIZE and 0 <= ny < GRID_SIZE):
                        continue

                    if (nx, ny) in blocked_set:
                        continue

                    if (nx, ny) in visited:
                        continue

                    visited.add((nx, ny))
                    queue.append((nx, ny))

            return len(visited) > BLOCK_LIMIT

        return bfs(source, target) and bfs(target, source)

The implementation begins by converting the blocked cells into a set for fast lookup. Since BFS repeatedly checks whether neighboring cells are blocked, constant time membership checks are essential for performance.

The variable BLOCK_LIMIT represents the maximum possible enclosed area formed by the blocked cells. This value determines when BFS can safely conclude that it has escaped confinement.

The helper function bfs performs a bounded breadth-first search. It explores neighboring cells while maintaining a visited set to prevent revisiting states.

The key optimization appears in the loop condition:

while queue and len(visited) <= BLOCK_LIMIT:

Once the number of visited cells exceeds the enclosure limit, the search immediately succeeds because the start point cannot be trapped.

The algorithm performs BFS twice:

  • from source to target
  • from target to source

This guarantees that neither endpoint is enclosed.

Go Solution

package main

import "container/list"

func isEscapePossible(blocked [][]int, source []int, target []int) bool {
	blockLimit := len(blocked) * (len(blocked) - 1) / 2
	gridSize := 1000000

	blockedSet := make(map[[2]int]bool)

	for _, cell := range blocked {
		blockedSet[[2]int{cell[0], cell[1]}] = true
	}

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

	bfs := func(start []int, finish []int) bool {
		queue := list.New()
		queue.PushBack([2]int{start[0], start[1]})

		visited := make(map[[2]int]bool)
		visited[[2]int{start[0], start[1]}] = true

		for queue.Len() > 0 && len(visited) <= blockLimit {
			front := queue.Front()
			queue.Remove(front)

			cell := front.Value.([2]int)
			x, y := cell[0], cell[1]

			if x == finish[0] && y == finish[1] {
				return true
			}

			for _, d := range directions {
				nx := x + d[0]
				ny := y + d[1]

				if nx < 0 || nx >= gridSize || ny < 0 || ny >= gridSize {
					continue
				}

				next := [2]int{nx, ny}

				if blockedSet[next] {
					continue
				}

				if visited[next] {
					continue
				}

				visited[next] = true
				queue.PushBack(next)
			}
		}

		return len(visited) > blockLimit
	}

	return bfs(source, target) && bfs(target, source)
}

The Go implementation follows the same logic as the Python version, but there are a few language-specific details.

Go does not have built-in tuple hashing, so fixed-size arrays like [2]int are used as hash map keys.

The BFS queue is implemented using container/list, since Go slices are inefficient for repeated front removals.

The visited set and blocked set are both implemented as maps from [2]int to bool.

Integer overflow is not an issue because all calculations remain well within Go's integer range.

Worked Examples

Example 1

blocked = [[0,1],[1,0]]
source = [0,0]
target = [0,2]

Blocked layout near the source:

Coordinate Status
(0,0) Source
(0,1) Blocked
(1,0) Blocked

The source is trapped in the corner.

BFS from source

Step Current Cell Queue Visited
1 (0,0) [] {(0,0)}

Neighbors checked:

Neighbor Result
(-1,0) Outside grid
(1,0) Blocked
(0,-1) Outside grid
(0,1) Blocked

No valid moves exist.

The queue becomes empty before escaping the enclosure limit.

Result:

false

Example 2

blocked = []
source = [0,0]
target = [999999,999999]

There are no blocked cells.

The enclosure limit becomes:

$\frac{0(0-1)}{2}=0$

The BFS immediately exceeds the limit after visiting the first cell.

BFS behavior

Step Visited Size Condition
Start 1 1 > 0

This proves the source is not enclosed.

The same logic applies to the target.

Result:

true

Complexity Analysis

Measure Complexity Explanation
Time O(B²) Each BFS explores at most the maximum enclosed area
Space O(B²) The visited set stores at most the bounded search region

Here:

  • B = len(blocked)
  • B <= 200

The maximum enclosed region formed by B blocked cells is bounded by:

$\frac{B(B-1)}{2}$

Since B <= 200, the algorithm explores at most about 20,000 cells per BFS. This makes the solution extremely efficient despite the enormous grid size.

Test Cases

sol = Solution()

# Example 1, source trapped immediately
assert sol.isEscapePossible(
    [[0, 1], [1, 0]],
    [0, 0],
    [0, 2]
) is False

# Example 2, completely open grid
assert sol.isEscapePossible(
    [],
    [0, 0],
    [999999, 999999]
) is True

# Single blocked cell does not matter
assert sol.isEscapePossible(
    [[10, 10]],
    [0, 0],
    [999999, 999999]
) is True

# Target enclosed
assert sol.isEscapePossible(
    [[0, 1], [1, 0], [1, 2], [2, 1]],
    [10, 10],
    [1, 1]
) is False

# Source enclosed
assert sol.isEscapePossible(
    [[0, 1], [1, 0], [1, 2], [2, 1]],
    [1, 1],
    [10, 10]
) is False

# Large coordinates near boundary
assert sol.isEscapePossible(
    [],
    [999998, 999998],
    [999999, 999999]
) is True

# Partial wall that does not fully enclose
assert sol.isEscapePossible(
    [[0, 1], [1, 1], [2, 1]],
    [0, 0],
    [3, 0]
) is True

# Small enclosed pocket
assert sol.isEscapePossible(
    [[1, 0], [0, 1], [1, 2], [2, 1]],
    [1, 1],
    [3, 3]
) is False

# Sparse blocked cells across grid
assert sol.isEscapePossible(
    [[100, 100], [200, 200], [300, 300]],
    [0, 0],
    [999999, 999999]
) is True

# Source and target close together
assert sol.isEscapePossible(
    [],
    [5, 5],
    [5, 6]
) is True

Test Summary

Test Why
Example 1 Validates immediate trapping at grid corner
Example 2 Validates empty blocked list
Single blocked cell Ensures isolated blocks do not matter
Target enclosed Confirms target-side BFS is necessary
Source enclosed Confirms source-side BFS works
Boundary coordinates Tests grid edge handling
Partial wall Ensures incomplete barriers do not fail
Small enclosed pocket Validates true enclosure detection
Sparse blocked cells Confirms large open traversal succeeds
Adjacent source/target Tests trivial reachable path

Edge Cases

Source Trapped at the Boundary

A particularly tricky case occurs when the source is near the edge of the grid and blocked cells cover the only valid exits.

For example:

source = [0,0]
blocked = [[0,1],[1,0]]

A careless implementation might assume there are always four neighboring moves available. However, two directions are invalid because they leave the grid.

The implementation correctly checks boundary conditions before exploring neighbors:

0 <= nx < GRID_SIZE and 0 <= ny < GRID_SIZE

This prevents invalid positions from entering the BFS queue.

Target Completely Enclosed

Another subtle issue is that the source may escape successfully while the target remains trapped.

If we only run BFS from the source, we could incorrectly conclude that escape is possible.

For example:

source = open area
target = enclosed pocket

The solution avoids this bug by running bounded BFS from both endpoints.

Only if both searches confirm escape do we return true.

No Blocked Cells

When blocked is empty, the enclosure limit becomes zero.

A naive implementation could accidentally terminate immediately without exploring anything.

The algorithm handles this naturally:

  • The starting cell itself counts as visited
  • len(visited) > 0
  • Therefore the BFS immediately proves the start is not enclosed

This correctly returns true for any two distinct coordinates in an open grid.