Escape a Large Maze
01 · Problem
Picture a huge grid of 10^6 x 10^6 cells, with coordinates (x, y) where 0 <= x, y < 10^6. A small list blocked marks the cells you may not enter; every other cell is open.
You start at source = [sx, sy] and want to reach target = [tx, ty]. In one move you may step to an adjacent cell (north, south, east or west) as long as it stays inside the grid and is not blocked.
Return true if the target can be reached from the source, otherwise false.
02 · Examples
blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
false
Both neighbours of the corner (0,0) are blocked, so the source is trapped and cannot reach (0,2).
blocked = [], source = [0,0], target = [999999,999999]
true
With nothing blocked, the opposite corner is reachable by walking along the edges of the grid.
blocked = [[0,2],[1,1],[2,0]], source = [5,5], target = [0,0]
false
The three blocked cells form a diagonal wall that seals the cells (0,0), (0,1) and (1,0) into the corner. The target is inside that pocket, so it cannot be reached.
03 · Constraints
- 010 <= blocked.length <= 200
- 02blocked[i].length == 2 and 0 <= blocked[i][j] < 106
- 03source.length == target.length == 2, with coordinates in [0, 106)
- 04source != target, and neither source nor target is blocked
- 05All blocked cells are distinct
04 · Optimal complexity
- Time
- O(b^2)
- Space
- O(b^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.