Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Escape a Large Maze solution and explanation

HardArrayBreadth-First SearchDepth-First SearchHash Table6 min read37.0% acceptanceUpdated 9 Apr 2026
Asked atUiPathGoogleAmazonMicrosoft
Practise Escape a Large Maze
29:12
Leetcode 1036(Hard) Escape a Large Maze: Simple C++ SolutionShivam Patel · 29:12 · 3K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode 1036(Hard) Escape a Large Maze: Simple C++ SolutionShivam Patel · 29:12 · 3K views
  2. LeetCode 1036. Escape a Large Maze Explanation and Solutionhappygirlzt · 10:05 · 3K views
  3. LeetCode 1036. Escape a Large Maze 中文解释 Chinese Versionhappygirlzt · 11:15 · 910 views
  4. 1036. Escape a Large Maze (Leetcode Hard)Programming Live with Larry · 28:05 · 804 views
  5. Baozi Training Leetcode 1036 solution: Escape a Large MazeBaozi Training · 11:26 · 701 views
  6. 【每日一题】1036. Escape a Large Maze, 09/10/2019Huifeng Guan · 53:18 · 376 views
  7. 猩猩的乐园 Leetcode 1036 Escape a Large Maze猩猩的乐园 · 9:10 · 315 views
  8. leetCode - 1036 Escape a Large Maze | JSer - algorithm & JavaScriptJSer · 38:54 · 286 views
  9. Leetcode 1036. Escape a Large Maze (bfs)LetsCode · 18:31 · 260 views
  10. Leetcode 1036. Escape a Large MazeAlgorithms for Big Bucks · 13:26 · 221 views

The problem

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).

We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).

Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.

Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation: The target square is inaccessible starting from the source square because we cannot move.
We cannot move north or east because those squares are blocked.
We cannot move south or west because we cannot go outside of the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation: Because there are no blocked cells, it is possible to reach the target square.

Constraints:

  • 0 <= blocked.length <= 200
  • blocked[i].length == 2
  • 0 <= xi, yi < 106
  • source.length == target.length == 2
  • 0 <= sx, sy, tx, ty < 106
  • source != target
  • It is guaranteed that source and target are not blocked.

Approach overview

Problem Overview: You are given a massive 1,000,000 x 1,000,000 grid with up to 200 blocked cells. Starting from a source cell, determine whether you can reach a target cell without stepping on blocked positions. The grid is too large for full exploration, so the solution relies on understanding how many cells the blocked positions can realistically enclose.

Approach 1: Breadth-First Search (BFS) with Enclosure Limit (O(b2) time, O(b2) space)

A naive BFS across the entire grid is impossible because the search space can reach 10^12 cells. The key insight is that the number of blocked cells (b ≤ 200) limits the maximum area they can surround. If blocked cells form a closed boundary, the largest enclosed region they can create is roughly b * (b - 1) / 2. Run a Breadth-First Search from the source while tracking visited cells using a hash table. If BFS reaches the target, return true immediately. If the search expands beyond the theoretical enclosure limit, the source is not trapped, so escape is possible.

To fully guarantee reachability, repeat the same bounded BFS from the target toward the source. This double check ensures neither endpoint is trapped by blocked cells. The algorithm only explores a few tens of thousands of cells at most, making it practical even with the huge grid size. Coordinates are generated by moving in four directions and skipping blocked or visited cells stored in hash sets.

Alternative: Depth-First Search with the Same Boundary Logic (O(b2) time, O(b2) space)

A Depth-First Search can replace BFS while using the same enclosure limit idea. DFS recursively explores neighbors and stops once the visited count exceeds the maximum possible enclosed area. Functionally the behavior is identical: if exploration escapes the theoretical boundary, the starting position cannot be trapped. BFS is generally preferred because it avoids deep recursion and handles frontier expansion more predictably in large grids.

Recommended for interviews: The bounded BFS approach is the expected solution. Interviewers want to see recognition that the grid size is a red herring and that the true constraint is the number of blocked cells. Explaining the enclosure limit (b * (b - 1) / 2) shows strong algorithmic reasoning. Implementing BFS with a hash set for blocked and visited coordinates demonstrates solid graph traversal fundamentals.

Approach 1: Approach 1: Breadth-First Search (BFS)

This approach leverages the Breadth-First Search (BFS) algorithm to explore the grid from the source point, while checking if the target can be reached without crossing any blocked squares. The BFS is limited by the number of blocked squares, as these block the path. Given that the blocked array is limited to at most 200, the BFS is bounded by a reasonable area since it cannot be contained by more than a certain number of blocked squares.

from collections import deque

class Solution:
    def isEscapePossible(self, blocked, source, target):
        blocked_set = set(map(tuple, blocked))
        return self.check(source, target, blocked_set) and self.check(target, source, blocked_set)

    def check(self, start, end, blocks):
        queue = deque([tuple(start)])
        visited = set(queue)
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        MAX_MOVES = len(blocks) * (len(blocks) - 1) // 2
        count = 0

        while queue and count < MAX_MOVES:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if (nx, ny) == tuple(end) or (0 <= nx < 10**6 and 0 <= ny < 10**6 
                    and (nx, ny) not in blocks and (nx, ny) not in visited):
                    queue.append((nx, ny))
                    visited.add((nx, ny))
            count += 1

        return count >= MAX_MOVES

if __name__ == '__main__':
    solution = Solution()
    blocked = [[0, 1], [1, 0]]
    source = [0, 0]
    target = [0, 2]
    print(solution.isEscapePossible(blocked, source, target))
import java.util.*;

class Solution {
    private static final int MAX = (int) 1e6;
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<Long> blockedSet = new HashSet<>();
        for (int[] b : blocked) {
            blockedSet.add(((long) b[0] << 20) | b[1]);
        }
        int maxSteps = blocked.length * (blocked.length - 1) / 2;
        return canReach(source, target, blockedSet, maxSteps) && canReach(target, source, blockedSet, maxSteps);
    }

    private boolean canReach(int[] start, int[] end, Set<Long> blocked, int maxSteps) {
        Set<Long> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1]});
        visited.add((((long) start[0]) << 20) | start[1]);

        int steps = 0;
        while (!queue.isEmpty() && steps < maxSteps) {
            int sz = queue.size();
            while (sz-- > 0) {
                int[] curr = queue.poll();
                for (int[] dir : DIRS) {
                    int nx = curr[0] + dir[0];
                    int ny = curr[1] + dir[1];
                    long hash = (((long) nx) << 20) | ny;
                    
                    if (nx < 0 || nx >= MAX || ny < 0 || ny >= MAX || visited.contains(hash) || blocked.contains(hash)) {
                        continue;
                    }

                    if (nx == end[0] && ny == end[1]) {
                        return true;
                    }

                    queue.offer(new int[]{nx, ny});
                    visited.add(hash);
                }
            }
            steps++;
        }
        return steps >= maxSteps;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] blocked = {{0, 1}, {1, 0}};
        int[] source = {0, 0};
        int[] target = {0, 2};

        System.out.println(sol.isEscapePossible(blocked, source, target));
    }
}
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

typedef pair<int, int> Point;

class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        const int MAX_MOVES = blocked.size() * (blocked.size() - 1) / 2;
        unordered_set<long> blocked_set;
        for (const auto& b : blocked) {
            blocked_set.insert(((long)b[0] << 20) | b[1]);
        }
        return canReach(source, target, blocked_set, MAX_MOVES) && canReach(target, source, blocked_set, MAX_MOVES);
    }

private:
    vector<Point> directions{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    bool canReach(vector<int>& start, vector<int>& target, unordered_set<long>& blocked, int max_moves) {
        unordered_set<long> visited;
        queue<Point> q;
        q.push({start[0], start[1]});
        visited.insert(((long)start[0] << 20) | start[1]);

        int moves = 0;
        while (!q.empty() && moves < max_moves) {
            int size = q.size();
            while (size--) {
                auto [x, y] = q.front();
                q.pop();

                for (const auto& dir : directions) {
                    int nx = x + dir.first;
                    int ny = y + dir.second;
                    long hash = ((long)nx << 20) | ny;

                    if (nx < 0 || nx >= 1e6 || ny < 0 || ny >= 1e6 || visited.count(hash) || blocked.count(hash)) {
                        continue;
                    }
                    if (nx == target[0] && ny == target[1]) {
                        return true;
                    }
                    q.push({nx, ny});
                    visited.insert(hash);
                }
            }
            moves++;
        }
        return moves >= max_moves;
    }
};

int main() {
    Solution s;
    vector<vector<int>> blocked{{0, 1}, {1, 0}};
    vector<int> source{0, 0};
    vector<int> target{0, 2};
    cout << (s.isEscapePossible(blocked, source, target) ? "true" : "false") << endl;
    return 0;
}
var isEscapePossible = function(blocked, source, target) {
    const HASH_MULTIPLIER = 1048576;
    const maxSteps = blocked.length * (blocked.length - 1) / 2;
    const blockedSet = new Set(blocked.map(b => b[0] * HASH_MULTIPLIER + b[1]));

    function bfs(start, end) {
        const queue = [];
        const visited = new Set();
        queue.push(start);
        visited.add(start[0] * HASH_MULTIPLIER + start[1]);
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        let steps = 0;

        while (queue.length && steps < maxSteps) {
            const [x, y] = queue.shift();
            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;
                const hash = nx * HASH_MULTIPLIER + ny;

                if (nx === end[0] && ny === end[1]) return true;

                if (nx >= 0 && nx < 1e6 && ny >= 0 && ny < 1e6 && !blockedSet.has(hash) && !visited.has(hash)) {
                    visited.add(hash);
                    queue.push([nx, ny]);
                }
            }
            steps++;
        }
        return steps >= maxSteps;
    }

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

console.log(isEscapePossible([[0, 1], [1, 0]], [0, 0], [0, 2]));
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000000
#define BLOCK_LIMIT 200
#define DIRECTIONS 4

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

bool bfs(int* source, int* target, bool grid[MAX_SIZE][MAX_SIZE]) {
    int sx = source[0], sy = source[1];
    int tx = target[0], ty = target[1];

    if (sx == tx && sy == ty) return true;
    
    int queue[MAX_SIZE * 2][2];
    int front = 0, rear = 0;
    queue[rear][0] = sx;
    queue[rear][1] = sy;
    rear++;

    bool visited[MAX_SIZE][MAX_SIZE] = {false};
    visited[sx][sy] = true;

    while (front < rear && rear < BLOCK_LIMIT * BLOCK_LIMIT) {
        int x = queue[front][0];
        int y = queue[front][1];
        front++;

        for (int i = 0; i < DIRECTIONS; ++i) {
            int nx = x + directions[i][0];
            int ny = y + directions[i][1];
            
            if (nx >= 0 && nx < MAX_SIZE && ny >= 0 && ny < MAX_SIZE && !grid[nx][ny] && !visited[nx][ny]) {
                if (nx == tx && ny == ty) return true;
                queue[rear][0] = nx;
                queue[rear][1] = ny;
                rear++;
                visited[nx][ny] = true;
            }
        }
    }

    return front < rear;
}

bool isEscapePossible(int blocked[][2], int blockedSize, int* source, int* target) {
    bool grid[MAX_SIZE][MAX_SIZE] = {false};
    
    for (int i = 0; i < blockedSize; ++i)
        grid[blocked[i][0]][blocked[i][1]] = true;

    return bfs(source, target, grid);
}

int main() {
    int blocked[][2] = {{0,1},{1,0}};
    int source[] = {0,0};
    int target[] = {0,2};
    
    printf("%s\n", isEscapePossible(blocked, sizeof(blocked)/sizeof(blocked[0]), source, target) ? "true" : "false");
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    private static readonly int MAX = (int)1e6;
    private static readonly int[][ ] DIRECTIONS = new int[][] {
        new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1}
    };

    public bool IsEscapePossible(int[][] blocked, int[] source, int[] target) {
        var blockedSet = new HashSet<long>();
        foreach (var b in blocked) {
            blockedSet.Add((long)b[0] << 20 | b[1]);
        }
        int maxMoves = blocked.Length * (blocked.Length - 1) / 2;
        return CanReach(source, target, blockedSet, maxMoves) && CanReach(target, source, blockedSet, maxMoves);
    }

    private bool CanReach(int[] start, int[] end, HashSet<long> blocked, int maxMoves) {
        var visited = new HashSet<long>();
        var queue = new Queue<int[]>();
        queue.Enqueue(new int[] {start[0], start[1]});
        visited.Add(((long)start[0] << 20) | start[1]);

        int steps = 0;
        while (queue.Count > 0 && steps < maxMoves) {
            int size = queue.Count;
            while (size-- > 0) {
                var current = queue.Dequeue();
                int x = current[0], y = current[1];
                foreach (var dir in DIRECTIONS) {
                    int nx = x + dir[0], ny = y + dir[1];
                    long hash = ((long)nx << 20) | ny;

                    if (nx < 0 || nx >= MAX || ny < 0 || ny >= MAX ||
                        visited.Contains(hash) || blocked.Contains(hash)) {
                        continue;
                    }

                    if (nx == end[0] && ny == end[1]) {
                        return true;
                    }

                    queue.Enqueue(new int[] { nx, ny });
                    visited.Add(hash);
                }
            }
            steps++;
        }

        return steps >= maxMoves;
    }

    public static void Main() {
        var solution = new Solution();
        int[][] blocked = { new int[]{ 0, 1 }, new int[]{ 1, 0 } };
        int[] source = { 0, 0 };
        int[] target = { 0, 2 };
        Console.WriteLine(solution.IsEscapePossible(blocked, source, target));
    }
}

The Python solution uses BFS with deque for queue efficiency and checks both from source to target and target to source with maximum exploration containd by block size.

Complexity

Time Complexity: O(B^2) due to exploration constraints, similar to other BFS approaches.

Space Complexity: O(B^2), primarily due to storage of visited nodes.

Try this approach in the editor

Approach 2: DFS

The problem can be interpreted as determining whether it is possible to move from a source point to a target point in a 10^6 times 10^6 grid, given a small number of blocked points.

Since the number of blocked points is small, the maximum area that can be blocked is no more than |blocked|^2 / 2. Therefore, we can perform a depth-first search (DFS) starting from both the source and the target points. The search continues until either the target point is reached or the number of visited points exceeds |blocked|^2 / 2. If either condition is satisfied, return true. Otherwise, return false.

Time complexity is O(m), and space complexity is O(m), where m is the size of the blocked region. In this problem, m leq |blocked|^2 / 2 = 200^2 / 2 = 20000.

function isEscapePossible(blocked: number[][], source: number[], target: number[]): boolean {
    const n = 10 ** 6;
    const m = (blocked.length ** 2) >> 1;
    const dirs = [-1, 0, 1, 0, -1];

    const s = new Set<number>();
    const f = (i: number, j: number): number => i * n + j;

    for (const [x, y] of blocked) {
        s.add(f(x, y));
    }

    const dfs = (sx: number, sy: number, tx: number, ty: number, vis: Set<number>): boolean => {
        vis.add(f(sx, sy));
        if (vis.size > m) {
            return true;
        }
        for (let k = 0; k < 4; k++) {
            const x = sx + dirs[k],
                y = sy + dirs[k + 1];
            if (x >= 0 && x < n && y >= 0 && y < n) {
                if (x === tx && y === ty) {
                    return true;
                }
                const key = f(x, y);
                if (!s.has(key) && !vis.has(key) && dfs(x, y, tx, ty, vis)) {
                    return true;
                }
            }
        }
        return false;
    };

    return (
        dfs(source[0], source[1], target[0], target[1], new Set()) &&
        dfs(target[0], target[1], source[0], source[1], new Set())
    );
}
func isEscapePossible(blocked [][]int, source []int, target []int) bool {
	const n = 1_000_000
	m := len(blocked) * len(blocked) / 2
	dirs := [5]int{-1, 0, 1, 0, -1}

	f := func(i, j int) int64 {
		return int64(i*n + j)
	}

	s := make(map[int64]bool)
	for _, b := range blocked {
		s[f(b[0], b[1])] = true
	}

	var dfs func(sx, sy, tx, ty int, vis map[int64]bool) bool
	dfs = func(sx, sy, tx, ty int, vis map[int64]bool) bool {
		key := f(sx, sy)
		vis[key] = true
		if len(vis) > m {
			return true
		}
		for k := 0; k < 4; k++ {
			x, y := sx+dirs[k], sy+dirs[k+1]
			if x >= 0 && x < n && y >= 0 && y < n {
				if x == tx && y == ty {
					return true
				}
				key := f(x, y)
				if !s[key] && !vis[key] && dfs(x, y, tx, ty, vis) {
					return true
				}
			}
		}
		return false
	}

	sx, sy := source[0], source[1]
	tx, ty := target[0], target[1]
	return dfs(sx, sy, tx, ty, map[int64]bool{}) && dfs(tx, ty, sx, sy, map[int64]bool{})
}
use std::collections::HashSet;

impl Solution {
    pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
        const N: i64 = 1_000_000;
        let m = (blocked.len() * blocked.len()) as i64 / 2;

        let f = |i: i64, j: i64| -> i64 { i * N + j };

        let mut s: HashSet<i64> = HashSet::new();
        for b in &blocked {
            s.insert(f(b[0] as i64, b[1] as i64));
        }

        fn dfs(
            sx: i64,
            sy: i64,
            tx: i64,
            ty: i64,
            s: &HashSet<i64>,
            m: i64,
            vis: &mut HashSet<i64>,
        ) -> bool {
            static DIRS: [i64; 5] = [-1, 0, 1, 0, -1];
            let key = sx * 1_000_000 + sy;
            vis.insert(key);
            if vis.len() as i64 > m {
                return true;
            }
            for k in 0..4 {
                let x = sx + DIRS[k];
                let y = sy + DIRS[k + 1];
                let key = x * 1_000_000 + y;
                if x >= 0 && x < 1_000_000 && y >= 0 && y < 1_000_000 {
                    if x == tx && y == ty {
                        return true;
                    }
                    if !s.contains(&key) && vis.insert(key) && dfs(x, y, tx, ty, s, m, vis) {
                        return true;
                    }
                }
            }
            false
        }

        dfs(
            source[0] as i64,
            source[1] as i64,
            target[0] as i64,
            target[1] as i64,
            &s,
            m,
            &mut HashSet::new(),
        ) && dfs(
            target[0] as i64,
            target[1] as i64,
            source[0] as i64,
            source[1] as i64,
            &s,
            m,
            &mut HashSet::new(),
        )
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Breadth-First Search (BFS)

Time Complexity: O(B^2) due to exploration constraints, similar to other BFS approaches.

Space Complexity: O(B^2), primarily due to storage of visited nodes.

DFS–

Complexity analysis

ApproachTimeSpaceWhen to Use
Naive BFS Over Entire GridO(10^12)O(10^12)Theoretical baseline; infeasible due to huge grid size
Bounded BFS with Enclosure LimitO(b^2)O(b^2)Optimal solution when blocked cells are small (b ≤ 200)
DFS with Boundary LimitO(b^2)O(b^2)Alternative traversal if recursion or stack-based exploration is preferred

Frequently asked questions

Is Escape a Large Maze easy or hard?

Escape a Large Maze is classified as a Hard problem. The challenge is not BFS itself but recognizing that the grid size makes naive exploration impossible. The key insight is the mathematical bound on the maximum area blocked cells can enclose.

Escape a Large Maze Python/Java solution

Implement BFS using a queue and store coordinates in a hash set for blocked and visited cells. Each step explores four directions (up, down, left, right) while ensuring coordinates stay inside the grid bounds. The traversal stops early if the visited count exceeds the enclosure threshold, guaranteeing efficiency in Python, Java, C++, or JavaScript.

How to solve Escape a Large Maze in O(b^2)?

Store blocked cells in a hash set and perform BFS from the source. Track visited cells and stop the search if the number of visited nodes exceeds b*(b-1)/2, which proves the region is not enclosed. Repeat the same bounded BFS from the target. If neither side is trapped, a path between them must exist.

What is the best approach for Escape a Large Maze?

The optimal approach uses Breadth-First Search with a bounded exploration limit. Because the number of blocked cells is at most 200, they can only enclose a region of about b*(b-1)/2 cells. If BFS from the source expands beyond that limit, the source is not trapped. Running the same check from the target ensures both endpoints can escape.

Is Escape a Large Maze asked at Google/Amazon/Meta?

Escape a Large Maze is a classic hard graph traversal problem frequently discussed in interviews at large tech companies. Variants involving large grids, blocked regions, and reachability checks appear in Google and Meta-style system reasoning interviews where candidates must optimize exploration strategies.

What data structure is used in Escape a Large Maze?

The solution primarily uses a queue for Breadth-First Search and a hash set to store blocked and visited coordinates. The hash set allows O(1) lookups to quickly check whether a cell is blocked or already explored while traversing the grid.

What is the time complexity of Escape a Large Maze?

The optimized solution runs in O(b^2) time where b is the number of blocked cells (maximum 200). BFS stops once it explores more than the maximum possible enclosed area, which keeps the search under about 20,000 cells. Space complexity is also O(b^2) due to the visited set.

Comments

Now write it yourselfClose this page and solve Escape a Large Maze in the editor, without looking.
Practise Escape a Large Maze