Escape a Large Maze

Hard
1692.

Escape a Large Maze

Escape a Large Maze is a hard coding problem on arrays, hash table and depth-first search, asked in Amazon and Google interviews.

There is a 10^6 x 10^6 grid on the XY-plane; each square has integer coordinates (x, y) with 0 <= x, y < 10^6.

You start at source = [sx, sy] and want to reach target = [tx, ty]. The squares listed in blocked (each [xi, yi]) cannot be entered. In one move you go one square north, east, south or west, and you may not leave the grid.

Return true if the target can be reached from the source, and false otherwise.

Example 1

Input
blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output
false
Explanation
The two blocked squares seal the corner square (0, 0) off from everything else.

Example 2

Input
blocked = [], source = [0,0], target = [999999,999999]
Output
true

Example 3

Input
blocked = [[1,0],[1,1],[1,2]], source = [0,0], target = [5,5]
Output
true
Explanation
The wall along x = 1 ends at y = 2, so the walker goes up column 0 and around it.

Constraints

  • 0 <= blocked.length <= 200
  • blocked[i].length == 2
  • 0 <= xi, yi < 10^6
  • source.length == target.length == 2
  • 0 <= sx, sy, tx, ty < 10^6
  • source != target
  • source and target are not blocked
  • all blocked squares are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} blocked
 * @param {number[]} source
 * @param {number[]} target
 * @return {boolean}
 */
var isEscapePossible = function(blocked, source, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Escape a Large Maze — Solution in Python, Java & C++

Escape a Large Maze solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Escape a Large Maze is a hard coding problem on arrays, hash table and depth-first search, asked in Amazon and Google interviews.

Problem statement

There is a 10^6 x 10^6 grid on the XY-plane; each square has integer coordinates (x, y) with 0 <= x, y < 10^6.

You start at source = [sx, sy] and want to reach target = [tx, ty]. The squares listed in blocked (each [xi, yi]) cannot be entered. In one move you go one square north, east, south or west, and you may not leave the grid.

Return true if the target can be reached from the source, and false otherwise.

Example 1

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation: The two blocked squares seal the corner square (0, 0) off from everything else.

Example 2

Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true

Example 3

Input: blocked = [[1,0],[1,1],[1,2]], source = [0,0], target = [5,5]
Output: true
Explanation: The wall along x = 1 ends at y = 2, so the walker goes up column 0 and around it.

Constraints

  • 0 <= blocked.length <= 200
  • blocked[i].length == 2
  • 0 <= xi, yi < 10^6
  • source.length == target.length == 2
  • 0 <= sx, sy, tx, ty < 10^6
  • source != target
  • source and target are not blocked
  • all blocked squares are distinct

Hints for Escape a Large Maze

  1. Hint 1

    The grid has 10^12 squares — searching it all is out of the question. Only the blocked squares can stop you, and there are at most 200 of them.

  2. Hint 2

    How large an area can k blocked squares enclose? Bending a wall against a corner of the grid is the best they can do: a diagonal of k squares encloses about k · (k - 1) / 2 squares.

  3. Hint 3

    BFS from the source but stop early: if you have visited more squares than k · (k - 1) / 2, you cannot be enclosed. Do the same from the target — both must escape (or meet).

How to solve Escape a Large Maze

A small wall can only enclose a small region. k blocked squares enclose at most k · (k - 1) / 2 free squares (a diagonal across a corner of the grid). So a bounded BFS either finds the target, runs out of squares (it is trapped), or exceeds that bound (it is free).

Approach

  1. Put the blocked squares in a hash set and let limit = k · (k - 1) / 2 for k = blocked.length.
  2. bfs(from, to): a BFS from from with a visited hash set. Return true as soon as to is reached or the visited count exceeds limit; return false if the queue empties first.
  3. Answer bfs(source, target) && bfs(target, source).

Why it works

If the source is enclosed, its region has at most limit squares and its BFS empties without exceeding the bound — unless the target is inside the same region, in which case it is found. If neither endpoint is enclosed, both lie in the single unbounded region that surrounds every blocked square (any two escaping squares are connected around the outside of the walls). The second search guards the case where the source is free but the target is enclosed.

Complexity

  • Time — O(k^2) — each BFS touches at most about k^2 / 2 squares
  • Space — O(k^2)

Pitfalls

  • Checking only from the source is wrong: the target may be the one sealed in.
  • Encode a square as one 64-bit key (x · 10^6 + y) — the product overflows 32 bits.
  • With zero or one blocked square nothing can be enclosed; the bound of 0 handles that automatically.

Reference solution

Python

from collections import deque
from typing import List

def isEscapePossible(blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
    SIDE = 10 ** 6
    block = {(x, y) for x, y in blocked}
    limit = len(blocked) * (len(blocked) - 1) // 2

    def bfs(src, dst):
        start = (src[0], src[1])
        goal = (dst[0], dst[1])
        seen = {start}
        q = deque([start])
        while q:
            x, y = q.popleft()
            for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                if 0 <= nx < SIDE and 0 <= ny < SIDE and (nx, ny) not in block and (nx, ny) not in seen:
                    if (nx, ny) == goal:
                        return True
                    seen.add((nx, ny))
                    if len(seen) > limit:
                        return True
                    q.append((nx, ny))
        return False

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

Java

public static boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
    Set<Long> block = new HashSet<>();
    for (int[] b : blocked) block.add((long) b[0] * 1000000 + b[1]);
    long limit = (long) blocked.length * (blocked.length - 1) / 2;
    return escBfs(block, limit, source, target) && escBfs(block, limit, target, source);
}

static boolean escBfs(Set<Long> block, long limit, int[] src, int[] dst) {
    final int SIDE = 1000000;
    int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    long goal = (long) dst[0] * SIDE + dst[1];
    Set<Long> seen = new HashSet<>();
    seen.add((long) src[0] * SIDE + src[1]);
    ArrayDeque<int[]> q = new ArrayDeque<>();
    q.add(src);
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        for (int k = 0; k < 4; k++) {
            int nx = cur[0] + dx[k], ny = cur[1] + dy[k];
            if (nx < 0 || ny < 0 || nx >= SIDE || ny >= SIDE) continue;
            long key = (long) nx * SIDE + ny;
            if (block.contains(key) || seen.contains(key)) continue;
            if (key == goal) return true;
            seen.add(key);
            if (seen.size() > limit) return true;
            q.add(new int[]{nx, ny});
        }
    }
    return false;
}

C++

static bool escBfs(unordered_set<long long>& block, long long limit, vector<int>& src, vector<int>& dst) {
    const int SIDE = 1000000;
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    long long goal = (long long)dst[0] * SIDE + dst[1];
    unordered_set<long long> seen{(long long)src[0] * SIDE + src[1]};
    queue<pair<int, int>> q;
    q.push({src[0], src[1]});
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= SIDE || ny >= SIDE) continue;
            long long key = (long long)nx * SIDE + ny;
            if (block.count(key) || seen.count(key)) continue;
            if (key == goal) return true;
            seen.insert(key);
            if ((long long)seen.size() > limit) return true;
            q.push({nx, ny});
        }
    }
    return false;
}

bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
    unordered_set<long long> block;
    for (auto& b : blocked) block.insert((long long)b[0] * 1000000 + b[1]);
    long long limit = (long long)blocked.size() * ((long long)blocked.size() - 1) / 2;
    return escBfs(block, limit, source, target) && escBfs(block, limit, target, source);
}

JavaScript

var isEscapePossible = function(blocked, source, target) {
    var SIDE = 1000000, block = {};
    for (var i = 0; i < blocked.length; i++) block[blocked[i][0] * SIDE + blocked[i][1]] = true;
    var limit = blocked.length * (blocked.length - 1) / 2;
    var dx = [1, -1, 0, 0], dy = [0, 0, 1, -1];
    var bfs = function(src, dst) {
        var goal = dst[0] * SIDE + dst[1];
        var seen = {}, count = 1;
        seen[src[0] * SIDE + src[1]] = true;
        var q = [src];
        for (var h = 0; h < q.length; h++) {
            for (var k = 0; k < 4; k++) {
                var nx = q[h][0] + dx[k], ny = q[h][1] + dy[k];
                if (nx < 0 || ny < 0 || nx >= SIDE || ny >= SIDE) continue;
                var key = nx * SIDE + ny;
                if (block[key] || seen[key]) continue;
                if (key === goal) return true;
                seen[key] = true;
                if (++count > limit) return true;
                q.push([nx, ny]);
            }
        }
        return false;
    };
    return bfs(source, target) && bfs(target, source);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets