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.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Depth-First Search, Breadth-First Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 200blocked[i].length == 20 <= xi, yi < 10^6source.length == target.length == 20 <= sx, sy, tx, ty < 10^6source != targetsource and target are not blockedall blocked squares are distinct
Hints for Escape a Large Maze
Hint 1
The grid has
10^12squares — searching it all is out of the question. Only the blocked squares can stop you, and there are at most 200 of them.Hint 2
How large an area can
kblocked squares enclose? Bending a wall against a corner of the grid is the best they can do: a diagonal ofksquares encloses aboutk · (k - 1) / 2squares.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
- Put the blocked squares in a hash set and let
limit = k · (k - 1) / 2fork = blocked.length. bfs(from, to): a BFS fromfromwith a visited hash set. Returntrueas soon astois reached or the visited count exceedslimit; returnfalseif the queue empties first.- 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 aboutk^2 / 2squares - 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