Escape a Large Maze

Hard

#0990Time: O(N*M) in the worst case, where N and M are the grid dimensions. This is far too slow for the given constraints.Space: O(N*M), where N and M are the dimensions of the grid (10^6 x 10^6). This is required for the `visited` set and is prohibitively large.1 company

Algorithms

Depth-First Search Breadth-First Search

Data structures

Array Hash Table

Companies

UiPath

Prompt

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 = [s_x, s_y] square and want to reach the target = [t_x, t_y] square. There is also an array of blocked squares, where each blocked[i] = [x_i, y_i] represents a blocked square with coordinates (x_i, y_i).

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 <= x_i, y_i < 10⁶
source.length == target.length == 2
0 <= s_x, s_y, t_x, t_y < 10⁶
source != target
It is guaranteed that source and target are not blocked.

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but impractical approach is to model the entire 10^6 x 10^6 grid as a graph and perform a standard traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). We would start at the source and explore adjacent cells, keeping track of visited cells to avoid cycles, until we either find the target or exhaust all reachable cells.

Algorithm

Treat the 10^6 x 10^6 grid as a graph.
Start a Breadth-First Search (BFS) or Depth-First Search (DFS) from the source coordinate.
Use a queue (for BFS) or stack (for DFS) to manage coordinates to visit.
Use a large hash set to keep track of visited coordinates to avoid cycles and redundant computations.
In each step, explore the four neighbors (north, east, south, west).
If a neighbor is within the grid boundaries, not blocked, and not visited, add it to the queue/stack and the visited set.
Continue the search until the target coordinate is found (return true) or the queue/stack becomes empty (return false).

Walkthrough

This method directly translates the problem into a graph traversal problem without considering the specific constraints. The grid cells are the nodes, and valid moves between adjacent cells are the edges. A standard BFS would guarantee finding the shortest path if one exists, but we only need to determine existence. However, the sheer size of the grid makes this approach infeasible. The number of cells is 10^12, so any algorithm that attempts to visit a significant fraction of the grid or store their visited status will fail due to time and memory constraints.

Complexity

Time

O(N*M) in the worst case, where N and M are the grid dimensions. This is far too slow for the given constraints.

Space

O(N*M), where N and M are the dimensions of the grid (10^6 x 10^6). This is required for the `visited` set and is prohibitively large.

Trade-offs

Pros

Conceptually simple and easy to understand.

Cons

Memory Limit Exceeded: The visited set could potentially store up to 10^12 coordinates, which is far beyond the memory capacity of any typical competitive programming environment.
Time Limit Exceeded: The search space is enormous. In an open grid, the search would explore a vast number of cells before reaching a distant target, leading to a timeout.

This approach leverages the crucial constraint that the number of blocked cells is very small (<= 200). These few blocks can only cordon off a finite, limited area. If the source is not trapped within such an area, it can access the vast, open parts of the grid. The same applies to the target. If both the source and target can reach this "open space," they can surely reach each other.

We can quantify the maximum possible area that can be enclosed. With B blocks, the largest area you can enclose is less than B*B / 2. We use this as a threshold. We perform a Breadth-First Search (BFS) from the source. If the search explores more cells than this threshold, we know the source isn't trapped. We do the same for the target. If both are not trapped, a path exists. This check also handles the case where the source and target are close and in the same enclosed region, as the BFS from source would find target directly.

Algorithm

Key Insight: A small number of blocks (B <= 200) can only enclose a relatively small area. The maximum area that B blocks can trap is B * (B - 1) / 2. For B=200, this is 19900 cells.
Strategy: If a point (source or target) can reach more cells than this maximum trappable area, it must be in an open region and can be considered to have "escaped". If both source and target can escape, they can reach each other through the vast open grid.
Implementation: We run two separate, bounded BFS searches: a. One from source to target. b. One from target to source.
Bounded BFS Logic (bfs(start, end)): a. Store blocked cells in a HashSet for O(1) lookups. b. Initialize a queue for BFS and a visited set. c. Set a limit for the search area, e.g., limit = blocked.length * (blocked.length - 1) / 2. d. Begin BFS from start. e. In the BFS loop, if visited.size() exceeds the limit, it means start has escaped. Return true. f. If the end point is found, a path exists. Return true. g. If the queue becomes empty before either of the above conditions is met, it means start is trapped in a small area that doesn't contain end. Return false.
Final Result: The function returns true only if both bfs(source, target) AND bfs(target, source) return true. This covers all cases: both are in a large open area, or both are in the same small enclosed area.

Walkthrough

The algorithm is implemented by creating a helper function, bfs(start, end, blockedSet, limit), which performs a bounded search. This function returns true if it either reaches end or if the number of visited cells surpasses the limit. It returns false if the reachable area from start is exhausted and is smaller than the limit and does not contain end.

The main function then calls this helper twice: bfs(source, target, ...) and bfs(target, source, ...). Both must be true for a path to be guaranteed. This correctly handles all scenarios:

Source and Target in the same small region: The first call finds the target and returns true. The second call finds the source and returns true. Result: true.
Source trapped, Target in open space: The first call returns false. Result: false.
Source and Target in different trapped regions: The first call returns false. Result: false.
Source and Target in open space: Both calls return true because their search areas will exceed the limit. Result: true.

To handle the large coordinates efficiently, we convert each (x, y) pair into a single long value (key = x * 10^6 + y) for use in HashSets.

1import java.util.HashSet;2import java.util.LinkedList;3import java.util.Queue;4import java.util.Set;5 6class Solution {7    private static final long GRID_SIZE = 1_000_000L;8    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};9 10    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {11        Set<Long> blockedSet = new HashSet<>();12        for (int[] block : blocked) {13            blockedSet.add((long)block[0] * GRID_SIZE + block[1]);14        }15 16        // With B blocks, the maximum area they can enclose is B*(B-1)/2.17        // If we visit more than this number of cells, we have escaped the enclosure.18        int limit = blocked.length * (blocked.length - 1) / 2;19 20        return bfs(source, target, blockedSet, limit) && bfs(target, source, blockedSet, limit);21    }22 23    private boolean bfs(int[] start, int[] end, Set<Long> blockedSet, int limit) {24        Queue<int[]> queue = new LinkedList<>();25        Set<Long> visited = new HashSet<>();26        27        long startKey = (long)start[0] * GRID_SIZE + start[1];28        long endKey = (long)end[0] * GRID_SIZE + end[1];29 30        queue.offer(start);31        visited.add(startKey);32 33        while (!queue.isEmpty()) {34            // If the number of visited cells exceeds the limit, we have escaped.35            if (visited.size() > limit) {36                return true;37            }38 39            int[] current = queue.poll();40 41            if ((long)current[0] * GRID_SIZE + current[1] == endKey) {42                return true;43            }44 45            for (int[] dir : dirs) {46                int nextX = current[0] + dir[0];47                int nextY = current[1] + dir[1];48                long nextKey = (long)nextX * GRID_SIZE + nextY;49 50                if (nextX >= 0 && nextX < GRID_SIZE &&51                    nextY >= 0 && nextY < GRID_SIZE &&52                    !blockedSet.contains(nextKey) &&53                    visited.add(nextKey)) { // .add() returns true if the element was new54                    55                    queue.offer(new int[]{nextX, nextY});56                }57            }58        }59        60        // If the queue is empty, we are trapped in a small area.61        return false;62    }63}

Complexity

Time

O(B^2), where B is the number of blocked cells. We perform two BFS runs, and each search explores at most `O(B^2)` cells. Creating the initial `blockedSet` takes O(B).

Space

O(B^2), where B is the number of blocked cells. The `visited` set and the BFS `queue` will store at most `O(B^2)` elements in the worst case for each of the two BFS runs.

Trade-offs

Pros

Highly Efficient: Avoids exploring the entire grid by limiting the search space based on the number of blocks.
Correctness: The logic correctly handles all cases, including when source/target are trapped or in open space.
Optimal Complexity: The time and space complexity are polynomial in the number of blocks, not the grid size, making it feasible.

Cons

The logic of needing two separate checks (source to target and target to source) might not be immediately intuitive.
Requires careful handling of large coordinates to use as keys in hash sets (e.g., converting (x, y) to a single long).

Solutions

Solution

1class Solution {2private3  int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};4private5  static final int N = (int)1 e6;6private7  Set<Integer> blocked;8public9  boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {10    this.blocked = new HashSet<>();11    for (int[] b : blocked) {12      this.blocked.add(b[0] * N + b[1]);13    }14    return dfs(source, target, new HashSet<>()) &&15           dfs(target, source, new HashSet<>());16  }17private18  boolean dfs(int[] source, int[] target, Set<Integer> seen) {19    int sx = source[0], sy = source[1];20    int tx = target[0], ty = target[1];21    if (sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 ||22        ty >= N || blocked.contains(sx * N + sy) ||23        seen.contains(sx * N + sy)) {24      return false;25    }26    seen.add(sx * N + sy);27    if (seen.size() > 20000 || (sx == target[0] && sy == target[1])) {28      return true;29    }30    for (int[] dir : dirs) {31      if (dfs(new int[]{sx + dir[0], sy + dir[1]}, target, seen)) {32        return true;33      }34    }35    return false;36  }37}

1typedef unsigned long long ULL ; class Solution { public: vector < vector < int >> dirs = { { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, { - 1 , 0 } }; unordered_set < ULL > blocked ; int N = 1e6 ; bool isEscapePossible ( vector < vector < int >>& blocked , vector < int >& source , vector < int >& target ) { this -> blocked . clear (); for ( auto & b : blocked ) this -> blocked . insert (( ULL ) b [ 0 ] * N + b [ 1 ]); unordered_set < ULL > s1 ; unordered_set < ULL > s2 ; return dfs ( source , target , s1 ) && dfs ( target , source , s2 ); } bool dfs ( vector < int >& source , vector < int >& target , unordered_set < ULL >& seen ) { int sx = source [ 0 ], sy = source [ 1 ]; int tx = target [ 0 ], ty = target [ 1 ]; if ( sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N || blocked . count (( ULL ) sx * N + sy ) || seen . count (( ULL ) sx * N + sy )) return 0 ; seen . insert (( ULL ) sx * N + sy ); if ( seen . size () > 20000 || ( sx == target [ 0 ] && sy == target [ 1 ])) return 1 ; for ( auto & dir : dirs ) { vector < int > next = { sx + dir [ 0 ], sy + dir [ 1 ]}; if ( dfs ( next , target , seen )) return 1 ; } return 0 ; } };

1class Solution:2    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool: def dfs(source, target, seen): x, y = source if (not (0 <= x < 10 ** 6 and 0 <= y < 10 ** 6) or (x, y) in blocked or (x, y) in seen): return False seen . add((x, y)) if len(seen) > 20000 or source == target: return True for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: next = [x + a, y + b] if dfs(next, target, seen): return True return False blocked = set((x, y) for x, y in blocked) return dfs(source, target, set()) and dfs(target, source, set())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem