1036. Escape a Large Maze LeetCode Solution
In this guide, you will get 1036. Escape a Large Maze LeetCode Solution with the best time and space complexity. The solution to Escape a Large Maze problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Escape a Large Maze solution in C++
- Escape a Large Maze solution in Java
- Escape a Large Maze solution in Python
- Additional Resources

Problem Statement of Escape a Large Maze
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.
Complexity Analysis
- Time Complexity:
- Space Complexity:
1036. Escape a Large Maze LeetCode Solution in C++
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source,
vector<int>& target) {
unordered_set<long> blockedSet;
for (const vector<int>& b : blocked)
blockedSet.insert(hash(b[0], b[1]));
return dfs(blockedSet, source[0], source[1], hash(target[0], target[1]),
{}) &&
dfs(blockedSet, target[0], target[1], hash(source[0], source[1]),
{});
}
private:
bool dfs(unordered_set<long>& blockedSet, int i, int j, long target,
unordered_set<long>&& seen) {
if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 ||
blockedSet.contains(hash(i, j)) || seen.contains(hash(i, j)))
return false;
seen.insert(hash(i, j));
if (seen.size() > (1 + 199) * 199 / 2 || hash(i, j) == target)
return true;
return dfs(blockedSet, i + 1, j, target, std::move(seen)) ||
dfs(blockedSet, i - 1, j, target, std::move(seen)) ||
dfs(blockedSet, i, j + 1, target, std::move(seen)) ||
dfs(blockedSet, i, j - 1, target, std::move(seen));
}
long hash(int i, int j) {
return (static_cast<long>(i) << 16) + j;
}
};
/* code provided by PROGIEZ */
1036. Escape a Large Maze LeetCode Solution in Java
class Solution {
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
Set<Long> blockedSet = new HashSet<>();
for (int[] b : blocked)
blockedSet.add(hash(b[0], b[1]));
return dfs(blockedSet, source[0], source[1], hash(target[0], target[1]), new HashSet<>()) &&
dfs(blockedSet, target[0], target[1], hash(source[0], source[1]), new HashSet<>());
}
private boolean dfs(Set<Long> blockedSet, int i, int j, long target, Set<Long> seen) {
if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 || blockedSet.contains(hash(i, j)) ||
seen.contains(hash(i, j)))
return false;
seen.add(hash(i, j));
if (seen.size() > (1 + 199) * 199 / 2 || hash(i, j) == target)
return true;
return //
dfs(blockedSet, i + 1, j, target, seen) || //
dfs(blockedSet, i - 1, j, target, seen) || //
dfs(blockedSet, i, j + 1, target, seen) || //
dfs(blockedSet, i, j - 1, target, seen);
}
private long hash(int i, int j) {
return ((long) i << 16) + j;
}
}
// code provided by PROGIEZ
1036. Escape a Large Maze LeetCode Solution in Python
class Solution:
def isEscapePossible(
self,
blocked: list[list[int]],
source: list[int],
target: list[int]
) -> bool:
def dfs(i: int, j: int, target: list[int], seen: set) -> bool:
if i < 0 or i >= 10**6 or j < 0 or j >= 10**6:
return False
if (i, j) in blocked or (i, j) in seen:
return False
seen.add((i, j))
return (len(seen) > (1 + 199) * 199 // 2 or [i, j] == target or
dfs(i + 1, j, target, seen) or
dfs(i - 1, j, target, seen) or
dfs(i, j + 1, target, seen) or
dfs(i, j - 1, target, seen))
blocked = set(tuple(b) for b in blocked)
return (dfs(source[0], source[1], target, set()) and
dfs(target[0], target[1], source, set()))
# code by PROGIEZ
Additional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.