1036. Escape a Large Maze

HardDepth-First SearchBreadth-First SearchArrayHash Table

Problem Description

The problem presents a situation where we have an infinitely large grid, and we want to determine if we can travel from a source cell to a target cell. The grid size mentioned is immense (1 million by 1 million), but the actual navigation is obstructed by a number of blocked cells, which cannot be passed through. The objective is to figure out whether it is possible to start from the source cell and reach the target cell by moving one cell at a time in any of the four cardinal directions (north, east, south, or west), without stepping on a blocked cell or going out of the grid's bounds. The specific task at hand is to confirm the reachability of the target cell from the source cell under these conditions.

Flowchart Walkthrough

To determine the most appropriate algorithm for LeetCode problem 1036, Escape a Large Maze, let's utilize the algorithm flowchart available here. We'll analyze the problem step by step based on the flowchart:

Is it a graph?
- Yes: The problem represents a grid as a graph with nodes as positions and edges as possible movements between positions.
Is it a tree?
- No: The graph represents a grid with possible restrictions (blocked cells), but it is not inherently hierarchical nor does it have a single root, so it can contain cycles.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The maze is not directed and can contain cycles, as one can potentially move in multiple directions and return to the same spot.
Is the problem related to shortest paths?
- No: The primary goal isn't to find the shortest path, but to determine if there's any path from one point to another, which involves exploring the space.
Does the problem involve connectivity?
- Yes: The main focus is to determine if there's a path connecting two points in the grid, making it a problem of checking connectivity between nodes (positions).
Is the graph weighted?
- No: Movement from one cell to another doesn’t have different "weights" or "costs"; it’s merely checking for paths.
Does the problem have small constraints?
- No (implicit): Depending on the size of the grid, the problem does not necessarily have small constraints; the maze can be fairly large, and the significant challenge is to avoid blocked areas effectively.

Based on the traversal through the flowchart, the problem directly pertains to checking for paths or connectivity in an unweighted scenario. This naturally lends itself to graph traversal techniques like DFS or BFS. Particularly, DFS is conventionally a useful way to explore paths in such scenarios due to its nature of diving deep into possible paths, which can efficiently determine connectivity or escape feasibility through potential complex pathways in the maze structure.

Conclusion: The flowchart recommends using DFS for this problem, as it helps in deeply exploring each possible route from the start point to determine if the end point can be reached, given the constraints of blocked cells.

Intuition

To solve this problem efficiently, considering the vast size of the grid, an exhaustive search approach (like breadth-first search or depth-first search through all possible paths) is not feasible for every possible movement. Instead, the solution uses a smarter strategy involving a depth-first search (DFS).

The insight behind the solution is that if there are enough free cells around the source or target then it is highly probable that a path exists. If a blockage exists, it will likely manifest within a relatively small vicinity of the start or end point. Therefore, we don't have to search the entire million by million grid; we only need to explore a reasonably sized area around the source and target.

In the provided solution code, a depth-first search (DFS) algorithm is applied, starting from the source and attempting to reach the target. The algorithm also starts again from the target and attempts to reach the source. This bidirectional approach can quickly determine whether a connection exists between these points because paths found from both sides are highly likely to intersect, given the vast size of the grid.

The DFS function tries to move from the current cell in all four possible directions and checks if any of the new cells either:

Go beyond the grid limits,
Are part of the set of blocked cells, or
Have been seen already in the current path.

If none of these conditions is met, the DFS continues to the next cell. To prevent the DFS from running indefinitely, a heuristic is used: if we have visited more than a certain number of cells (20,000 in this case), we assume that it is possible to escape, given the low probability of still being trapped after traversing through so many cells. This heuristic is based on the theory that if there were an enclosing blockade, it would have been encountered within a much smaller area.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution approach makes use of a depth-first search (DFS) strategy. DFS is a common algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Data Structures Used:

Sets: Both the blocked cells and the cells that have been seen during the DFS traversal are stored in sets. This is because set operations such as checking for membership ((x,y) in blocked) are very efficient, allowing the solution to quickly determine if a cell is blocked or has already been visited.

Functions:

dfs Function: This function is a recursive function used for DFS traversal. It takes a source (current cell), target cell, and a seen set (cells already visited) as inputs. It tries to reach the target by recursively exploring north, east, south, and west directions, while avoiding blocked cells and previously visited cells.

Implementation Details:

Initialization: The set of blocked cells is constructed at the beginning to have easy, fast access to whether a cell is blocked.
Boundary Conditions: In the recursive dfs function, the first condition checks whether the current cell is within the grid bounds, ensuring we do not step outside the 1 million by 1 million grid.
Blocked and Seen Checks: The function then checks if the current cell is blocked or has already been seen (visited). If either condition is true, the function returns False, as the path is not valid.
Termination Heuristic: The seen set is used to track the number of unique cells visited. If the size of the seen set exceeds 20,000, the function assumes it is possible to reach the target, as explained in the intuition part. If the current cell is the target, it means the target has been reached, and True is returned.
Recursive Exploration: When the aforementioned conditions fail, the function proceeds to generate the next possible moves by iterating through the different directions with offsets [[0, -1], [0, 1], [1, 0], [-1, 0]]. It then calls itself recursively (dfs) with each new coordinate as the source.
Bidirectional Search: The primary function isEscapePossible calls the DFS function twice, first with source to target, and then with target to source. Both calls must return True for the overall function to return True.

By using DFS and bidirectional search, the problem is solved effectively through localized exploration around the source and target areas. The 20,000-step heuristic ensures that even in the absence of a clear path, we avoid lengthy and unnecessary traversals, relying on probability to assert the likely existence of a path in such a vastly sized grid.

The combination of these techniques allows the solution to efficiently predict the possibility of reaching the target from the source without having to traverse every possible path in the massive grid space.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Imagine a grid that is a 5x5 section extracted from the infinitely large grid mentioned in the problem description. In this grid, let's consider the source cell to be at coordinates (0,0) and the target cell to be at coordinates (4,4). Now, let's place some blocked cells at coordinates (1,1), (2,1), and (3,1). Our aim is to find a path from the source to the target.

Step-by-Step Breakdown:

Initialization: The set of blocked cells contains (1,1), (2,1), and (3,1).
First DFS Call (Source to Target): We call the dfs function with the source at (0,0), the target at (4,4), and an initially empty seen set.

a. The function checks that (0,0) is within the grid, not blocked, and not seen before, so it adds (0,0) to the seen set.

b. The function then tries to explore adjacent cells (0,-1), (0,1), (1,0), and (-1,0). Since (0,-1) and (-1,0) are outside the grid, and (1,0) is a valid, unblocked, and unseen cell, the DFS continues to (1,0).

c. At (1,0), the process repeats, exploring adjacent cells. Since (1,1) is blocked, DFS will try (2,0).

d. This process continues following a pattern that avoids blocked and previously seen cells, aiming to find the target.

e. If at any point the size of the seen set exceeds 20,000 (not possible in this small grid, but applicable in the actual problem), the function will return True.

f. If the target cell (4,4) is reached, the function returns True.
Second DFS Call (Target to Source): Assuming the first DFS call returned True, a second DFS is initiated from target to source, following similar steps.
Outcome: For our example, the DFS would successfully find paths that bypass the blocked cells and reach the target, for both source to target and target to source, resulting in the overall function returning True.

This example demonstrates how the DFS function operates around obstacles and why we don't need to explore every cell, relying on heuristic and bidirectional search to confirm reachability in such a vast space.

Solution Implementation

1class Solution:
2    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
3        # Helper function to perform depth-first search
4        def dfs(current, target, seen):
5            # Unpack the current coordinates
6            x, y = current
7            # Check if the current position is out of bounds, blocked or already seen
8            if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen:
9                return False
10            # Mark the current position as seen
11            seen.add((x, y))
12            # If the number of seen positions is large enough or the target is reached, return True.
13            # The choice of 20000 is because in the worst case, the blocked area can form a perimeter which
14            # encloses an area of roughly 20000 squares (theoretical upper bound given by the problem constraints).
15            if len(seen) > 20000 or current == target:
16                return True
17            # Explore all four neighboring positions
18            for delta_x, delta_y in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
19                next_position = [x + delta_x, y + delta_y]
20                if dfs(next_position, target, seen):
21                    return True
22            return False
23
24        # Convert the list of blocked positions into a set for faster lookup
25        blocked = set(map(tuple, blocked))
26        # Perform dfs from both the source to the target, and the target to the source
27        # to check if both paths are unblocked.
28        return dfs(source, target, set()) and dfs(target, source, set())
29

1import java.util.HashSet;
2import java.util.Set;
3
4public class Solution {
5    // Directions representing the possible moves (up, down, left, right)
6    private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
7    // A large number used for hashing 2D coordinates into a single number
8    private static final int BASE = (int) 1e6;
9    // Set to store the blocked cells as hashed integers
10    private Set<Integer> blockedSet;
11
12    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
13        // Initialize the hash set of blocked coordinates
14        blockedSet = new HashSet<>();
15        for (int[] block : blocked) {
16            blockedSet.add(block[0] * BASE + block[1]);
17        }
18      
19        // Check if both source to target and target to source are reachable
20        return isReachable(source, target, new HashSet<>()) && isReachable(target, source, new HashSet<>());
21    }
22
23    // Helper method to perform DFS and check if a path exists
24    private boolean isReachable(int[] current, int[] target, Set<Integer> visited) {
25        // Coordinate decompression from the current cell
26        int x = current[0], y = current[1];
27      
28        // Check if current is out of bounds, is blocked, or has been visited already
29        if (x < 0 || x >= BASE || y < 0 || y >= BASE || blockedSet.contains(x * BASE + y) || visited.contains(x * BASE + y)) {
30            return false;
31        }
32      
33        // Mark the current cell as visited
34        visited.add(x * BASE + y);
35      
36        // If we have checked a certain number of steps or reached the target, return true
37        if (visited.size() > 20000 || (x == target[0] && y == target[1])) {
38            return true;
39        }
40      
41        // Explore in all four directions
42        for (int[] direction : DIRECTIONS) {
43            int newX = x + direction[0];
44            int newY = y + direction[1];
45            // Continue the search from the new cell
46            if (isReachable(new int[] {newX, newY}, target, visited)) {
47                return true;
48            }
49        }
50      
51        return false;
52    }
53}
54

1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5typedef unsigned long long ULL;
6
7class Solution {
8public:
9    vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
10    unordered_set<ULL> blockedSet;
11    const int GRID_SIZE = 1e6;
12
13    // Checks if it's possible to escape from source to target given a list of blocked cells.
14    bool isEscapePossible(vector<vector<int>>& blockedCells, vector<int>& source, vector<int>& target) {
15        // Reset the hashed set of blocked cells for a new escape query.
16        blockedSet.clear();
17        // Hashing each block cell position into a single number and storing it in blockedSet.
18        for (auto& cell : blockedCells) {
19            blockedSet.insert(static_cast<ULL>(cell[0]) * GRID_SIZE + cell[1]);
20        }
21      
22        // Create two sets to keep track of visited cells for both directions.
23        unordered_set<ULL> visitedFromSource;
24        unordered_set<ULL> visitedFromTarget;
25      
26        // Run bidirectional DFS to see if both source and target can reach each other.
27        return dfs(source, target, visitedFromSource) && dfs(target, source, visitedFromTarget);
28    }
29
30    // Depth First Search to find a path from source to target, avoiding blocked cells.
31    bool dfs(vector<int>& source, vector<int>& target, unordered_set<ULL>& visited) {
32        int currentX = source[0], currentY = source[1];
33        int targetX = target[0], targetY = target[1];
34
35        // Check if out of bounds, at a blocked cell, or the cell has already been visited.
36        if (currentX < 0 || currentX >= GRID_SIZE || currentY < 0 || currentY >= GRID_SIZE ||
37            targetX < 0 || targetX >= GRID_SIZE || targetY < 0 || targetY >= GRID_SIZE ||
38            blockedSet.count(static_cast<ULL>(currentX) * GRID_SIZE + currentY) ||
39            visited.count(static_cast<ULL>(currentX) * GRID_SIZE + currentY)) {
40            return false;
41        }
42
43        // Mark the current cell as visited.
44        visited.insert(static_cast<ULL>(currentX) * GRID_SIZE + currentY);
45
46        // If we have visited enough cells or reached the target, consider it possible to escape.
47        if (visited.size() > 20000 || (currentX == targetX && currentY == targetY)) {
48            return true;
49        }
50
51        // Explore in all 4 directions.
52        for (auto& dir : directions) {
53            vector<int> next = {currentX + dir[0], currentY + dir[1]};
54            if (dfs(next, target, visited)) {
55                return true;
56            }
57        }
58        return false;
59    }
60};
61

1type Point = [number, number]; // Represents a point in the grid.
2
3const GRID_SIZE: number = 1e6; // The size of the grid.
4let blockedSet: Set<number> = new Set(); // Set to keep track of blocked cells.
5const directions: Point[] = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // Possible directions of movement.
6
7// Hash a 2D grid position to a unique number.
8function hashPosition(x: number, y: number): number {
9    return x * GRID_SIZE + y;
10}
11
12// Checks if it's possible to escape from source to target given a list of blocked cells.
13function isEscapePossible(blockedCells: Point[], source: Point, target: Point): boolean {
14    blockedSet.clear(); // Reset the set for new escape query.
15    // Fill up the set with the hashed positions of blocked cells.
16    blockedCells.forEach(cell => {
17        blockedSet.add(hashPosition(cell[0], cell[1]));
18    });
19
20    let visitedFromSource: Set<number> = new Set();
21    let visitedFromTarget: Set<number> = new Set();
22
23    // Run bidirectional DFS to see if both source and target can reach each other.
24    return dfs(source, target, visitedFromSource) && dfs(target, source, visitedFromTarget);
25}
26
27// Depth First Search to find a path from source to target, avoiding blocked cells.
28function dfs(source: Point, target: Point, visited: Set<number>): boolean {
29    const [currentX, currentY] = source;
30    const [targetX, targetY] = target;
31
32    // Check if current position is out of bounds, blocked, or already visited.
33    if (currentX < 0 || currentX >= GRID_SIZE || currentY < 0 || currentY >= GRID_SIZE ||
34         blockedSet.has(hashPosition(currentX, currentY)) ||
35         visited.has(hashPosition(currentX, currentY))) {
36        return false;
37    }
38
39    // Mark the current position as visited.
40    visited.add(hashPosition(currentX, currentY));
41
42    // If the number of visited cells is over a threshold or we've reached the target, escape is possible.
43    if (visited.size > 20000 || (currentX === targetX && currentY === targetY)) {
44        return true;
45    }
46
47    // Try to move in each direction to find a path.
48    for (let dir of directions) {
49        const nextX = currentX + dir[0];
50        const nextY = currentY + dir[1];
51        if (dfs([nextX, nextY], target, visited)) {
52            return true;
53        }
54    }
55
56    return false;
57}
58

Time and Space Complexity

The time complexity of the provided code is O(B + (D^2)), where B is the number of blocked cells and D is the distance that needs to be traversed in the worst case. This is because the dfs function is called twice — once from the source to the target, and once from the target to the source. Each call to dfs can potentially explore up to 20,000 cells due to the check if len(seen) > 20000. This check works as an early termination condition; without this condition, the algorithm would have had a time complexity of O((10^6)^2), which is the total number of cells. However, since blocked is a set, the check (x, y) in blocked can be performed in O(1) time on average, leading to the time complexity of the exploration to be O(D^2). The initial transformation of the blocked list into a set also takes O(B) time, where B is the size of the blocked list.

The space complexity of the code is O(B + D), where B is the number of elements in the blocked list that is converted into a set and D is the maximum depth of the dfs recursion stack. The effective limit of the recursion stack is based on the early termination condition when len(seen) exceeds 20,000. The seen set also contributes to the space complexity, which in the worst case will hold the same number of elements as the depth of dfs. So, the space needed is dependent on the number of blocked cells and the recursive depth that results from the early stopping of the search once 20,000 cells have been seen.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know