Escape a Large Maze - Practice Coding Problems

Escape a Large Maze - Problem

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.

Input & Output

Example 1 — No Blocked Cells

$ Input: blocked = [], source = [0,0], target = [999999,999999]

› Output: true

💡 Note: With no blocked cells, we can always reach any cell from any other cell in the grid.

Example 2 — Source is Enclosed

$ Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]

› Output: false

💡 Note: The source [0,0] is blocked by cells [0,1] and [1,0], forming a corner trap that prevents reaching [0,2].

Example 3 — Path Exists Around Blocks

$ Input: blocked = [[0,1]], source = [0,0], target = [0,2]

› Output: true

💡 Note: Even with [0,1] blocked, we can go from [0,0] → [1,0] → [1,1] → [1,2] → [0,2] to reach the target.

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.

Visualization

Tap to expand

Understanding the Visualization

Input

Grid with source, target, and blocked cells

Process

Check if path exists using BFS with area limits

Output

Return true if path exists, false if blocked

Key Takeaway

🎯 Key Insight: Any enclosure formed by B blocked cells has maximum area B*(B-1)/2, allowing efficient detection of trapped positions

Asked in

G Google 15 a Amazon 8

The key insight is that with at most 200 blocked cells, any enclosed area has maximum size 200×199/2 = 19,900 cells. The optimal approach uses bidirectional BFS with area limits - if we explore more than this limit from either source or target, we know that point isn't trapped. Time: O(B²), Space: O(B²) where B is the number of blocked cells.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force BFS	O(10¹²)	O(10¹²)	Simple BFS exploration of entire reachable area
Optimized BFS with Area Limit	O(B²)	O(B²)	BFS with early termination using maximum enclosure area

Brute Force BFS — Algorithm Steps

Convert blocked array to set for O(1) lookup
Start BFS from source
Explore all 4 directions from each cell
Return true if target is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start BFS from source, mark blocked cells

Explore

Visit all adjacent unblocked cells level by level

Result

Return true if target is reached, false otherwise

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int** blocked, int blockedSize, int* blockedColSize, int* source, int sourceSize, int* target, int targetSize) {
    // Simplified implementation for demo
    if (blockedSize == 0) return true;
    
    // In a real implementation, we would need:
    // 1. Hash set for blocked positions
    // 2. BFS queue implementation
    // 3. Visited set implementation
    
    return true; // Placeholder
}

int main() {
    // Parse inputs (simplified)
    int source[2] = {0, 0};
    int target[2] = {999999, 999999};
    int** blocked = NULL;
    int blockedSize = 0;
    int* blockedColSize = NULL;
    
    bool result = solution(blocked, blockedSize, blockedColSize, source, 2, target, 2);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10¹²)

In worst case, might explore the entire 10⁶ × 10⁶ grid

✓ Linear Growth

Space Complexity

O(10¹²)

BFS queue and visited set could contain millions of cells

✓ Linear Space

18.5K Views

Medium Frequency

~35 min Avg. Time

432 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler