How do you solve Nearest Exit from Entrance in Maze?

Use BFS starting from the entrance cell. Mark the entrance as visited in-place (set maze[sr][sc] = '+') so it is never re-enqueued and is never treated as an exit. At each BFS layer, increment the step count. For each neighbor, if it is an open cell and on the boundary (and not the entrance), return the current step count as the shortest path. Otherwise, add it to the queue and mark visited. If BFS completes without finding an exit, return -1.

What pattern does Nearest Exit from Entrance in Maze use?

The Pattern: BFS (Shortest Path on Unweighted Grid) The Heuristic: When searching for the shortest path in a grid or graph where each move has equal cost, BFS guarantees the minimal number of steps by exploring neighbors layer by layer and returning immediately upon reaching the target.

Nearest Exit from Entrance in Maze — BFS

Q: What is the time complexity of Nearest Exit from Entrance in Maze?

O(m * n). Each cell is visited at most once. The BFS queue processes each reachable cell once, resulting in O(m*n) time for an m by n maze.

Problem

Given a 2D grid maze of '.' and '+' characters and an entrance coordinate, return the minimum number of steps to reach the nearest exit from the entrance, where an exit is any open cell on the maze boundary different from the entrance. Return -1 if no exit is reachable.

maze.length == m
maze[i].length == n
1 ≤ m, n ≤ 100
maze[i][j] is either '.' or '+'
entrance.length == 2
0 ≤ entrance[0] < m
0 ≤ entrance[1] < n
maze[entrance[0]][entrance[1]] == '.'

Example

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]

Output: 2

We need the nearest exit (an empty '.' cell on the boundary), but the entrance itself never counts as an exit. Start at entrance (1,0). We run BFS because every move has equal cost (1 step), so BFS explores cells in increasing distance. Layer 1 (steps = 1): - From (1,0), the only open neighbor is (1,1). Enqueue (1,1) and mark it visited. Layer 2 (steps = 2): - From (1,1), we can reach (1,2). This cell is on the boundary and is an exit. - Because BFS reaches (1,2) at the earliest possible layer, 2 is the minimum number of steps. Return 2.

Approach

Straightforward Solution

A brute-force approach might attempt all paths via DFS, but this does not guarantee the shortest path and can be inefficient due to repeated exploration.

Core Observation

The shortest path in an unweighted grid from a single source to the nearest exit is found by exploring neighbors in layers, ensuring the first exit found is the closest.

Path to Optimal

Preview

Recognizing the problem as a shortest path in an unweighted grid signals BFS as the optimal approach. BFS explores all nodes at distance d before nodes at distance d+1, ensuring the first exit found is the nearest…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use BFS starting from the entrance cell. Mark the entrance as visited in-place (set maze[sr][sc] = '+') so it is never re-enqueued and is never treated as an exit…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is visited at most once. The BFS queue processes each reachable cell once, resulting in O(m*n) time for an m by n maze.

Space

O(m * n)

The queue and visited markings can hold up to O(m*n) cells in the worst case, which is necessary to track explored states and prevent revisiting.

Solution

Python

1from collections import deque
2
3class Solution:
  def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
      m, n = len(maze), len(maze[0])
      sr, sc = entrance
7
      q = deque([(sr, sc)])
      maze[sr][sc] = '+'  
10
      steps = 0
      directions = [(1,0), (-1,0), (0,1), (0,-1)]
13
      while q:
          steps += 1
          for _ in range(len(q)):
              r, c = q.popleft()
18
              for dr, dc in directions:
                  nr, nc = r + dr, c + dc
                  if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':
                      if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                          return steps
                      maze[nr][nc] = '+'
                      q.append((nr, nc))
26
      return -1

Step-by-Step Solution

1

Initialize BFS Queue and Mark Entrance as Visited

5m, n = len(maze), len(maze[0])
6sr, sc = entrance
8q = deque([(sr, sc)])
9maze[sr][sc] = '+'  

Objective

To set up the BFS starting point with the entrance cell and mark it as visited to avoid revisiting.

Key Insight

Marking the entrance as visited in-place (setting it to '+') prevents revisiting the start and guarantees the entrance is not counted as an exit even if it lies on the boundary. Initializing the queue with the entrance coordinates sets the stage for layer-by-layer exploration. This ensures the BFS only explores valid paths and does not revisit cells, maintaining correctness and efficiency.

Interview Quick-Check

Core Logic

Marking the entrance as visited before BFS begins prevents cycles and ensures the entrance is not considered an exit.

State & Boundaries

Initialize the queue with the entrance coordinates to start BFS from the correct source.

Common Pitfalls & Bugs

Failing to mark the entrance as visited can cause infinite loops or incorrect exit detection.

2

Perform BFS Layer-by-Layer to Find Nearest Exit

To explore the maze in increasing order of distance from the entrance, checking neighbors and returning the step count upon reaching an exit.

3

Return -1 if No Exit is Reachable

To signal that no path to an exit exists after BFS exhausts all reachable cells.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 23 Critical

return steps

Return the current step count as the shortest path length to the exit.

Returning immediately upon finding an exit leverages BFS's guarantee that this is the minimal number of steps required.

Line 9 Critical

maze[sr][sc] = '+'

Mark the entrance cell as visited by setting it to '+'.

Marking the entrance as visited prevents revisiting it during BFS, avoiding infinite loops and incorrect exit detection.

Line 21 Critical

if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':

Check if the neighbor is within maze bounds and is an open cell ('.').

Validating neighbors prevents out-of-bounds errors and ensures BFS only explores traversable cells.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does BFS guarantee that the first exit found is the nearest exit in terms of steps?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Nearest Exit from Entrance in Maze from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Nearest Exit from Entrance in Maze drill

or drill a free problem

1	`from collections import deque`
2
3	`class Solution:`
4	`def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:`
5	`m, n = len(maze), len(maze[0])`
6	`sr, sc = entrance`
7
8	`q = deque([(sr, sc)])`
9	`maze[sr][sc] = '+'`
10
11	`steps = 0`
12	`directions = [(1,0), (-1,0), (0,1), (0,-1)]`
13
14	`while q:`
15	`steps += 1`
16	`for _ in range(len(q)):`
17	`r, c = q.popleft()`
18
19	`for dr, dc in directions:`
20	`nr, nc = r + dr, c + dc`
21	`if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':`
22	`if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:`
23	`return steps`
24	`maze[nr][nc] = '+'`
25	`q.append((nr, nc))`
26
27	`return -1`

5	`m, n = len(maze), len(maze[0])`
6	`sr, sc = entrance`
8	`q = deque([(sr, sc)])`
9	`maze[sr][sc] = '+'`