Nearest Exit from Entrance in Maze — BFS Shortest Path

Problem Statement#

LeetCode 1926 — Nearest Exit from Entrance in Maze (Medium)

You are given an m x n character matrix maze where '+' denotes a wall and '.' denotes an empty cell. You are also given the entrance position [entranceRow, entranceCol].

An exit is any empty cell on the border of the maze, excluding the entrance cell itself. Return the minimum number of steps to reach the nearest exit. Return -1 if no exit exists.

Constraints:

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

Example 1:

maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]]
entrance = [1,2]
 
Output: 1
Explanation: The entrance is at (1,2). The nearest exit is at (0,2), exactly 1 step away.

Example 2:

maze = [["+","+","+"],[".",".","."],["+","+","+"]]
entrance = [1,0]
 
Output: 2
Explanation: The entrance is on the border at (1,0), but it doesn't count as an exit.
The nearest exit is at (1,2), which is 2 steps away.

Example 3:

maze = [[".","+"]]
entrance = [0,0]
 
Output: -1
Explanation: The entrance is the only empty border cell; there is no valid exit.

Why This Problem Matters#

This is one of the cleanest examples of BFS for shortest path on a grid. Interviewers love it because it tests several things simultaneously:

1. BFS vs DFS intuition — can you immediately recognize that "minimum steps" demands BFS, not DFS?
2. Exit condition design — the entrance is a border cell but not a valid exit. Can you handle that edge case precisely?
3. In-place visited marking — marking cells as visited by turning them into walls avoids a separate visited array. Do you think of that optimization?

The problem also appears as a building block in more complex maze and path-finding problems. The same BFS template with a tweaked exit condition solves dozens of similar questions. Mastering this one makes problems like LC 994 (Rotting Oranges) and LC 1293 (Shortest Path in a Grid with Obstacles) feel familiar immediately.

The Core Insight#

BFS explores cells level by level, where each level corresponds to one more step from the entrance. The first time BFS reaches a border empty cell that is not the entrance, it has found the minimum-step exit — stop and return.

The key subtleties:

• Mark the entrance as visited immediately (turn it to '+'). Otherwise BFS might circle back to the entrance and count it as an exit on a later step.
• Check for exit on dequeue, not enqueue. Actually, it is more efficient to check immediately when expanding neighbors: if a neighbor is on the border, return its distance immediately without enqueuing.
• Border detection: a cell (r, c) is on the border if r == 0 or r == R-1 or c == 0 or c == C-1.

Visual Dry Run#

maze (entrance = [1,2]):
  + + . +
  . . . +
  + + + .
 
Step 0: enqueue (1,2), mark (1,2) as visited (+).
  Queue: [(1,2,0)]
 
Step 1: dequeue (1,2,0). Neighbors:
  (0,2) — empty, on border → return 0+1 = 1 ✓
  (2,2) — wall (+), skip
  (1,1) — empty, not border → enqueue (1,1,1), mark visited
  (1,3) — wall (+), skip
 
Answer: 1 step

Notice we return the moment we find a border cell — we don't finish exploring the entire maze.

Common Mistakes#

1. Not marking the entrance visited before BFS starts. If the entrance is on the border (e.g., [1,0]), and you don't mark it immediately, BFS might later find it again as a "border empty cell" and incorrectly return it as an exit.

2. Checking for exit on enqueue instead of during expansion. Both approaches work, but checking during expansion (when you find a neighbor that is on the border) lets you return immediately without one extra dequeue cycle.

3. Forgetting that a border entrance is not an exit. The problem explicitly excludes the entrance from being a valid exit. Marking it visited at the start handles this automatically.

4. Using DFS for "minimum steps." DFS finds A path, not necessarily the shortest. Only BFS guarantees the shortest path in an unweighted graph.

5. Off-by-one in border detection. Using r <= 0 instead of r == 0, or checking r < R-1 instead of r == R-1. The border is the outermost ring of cells.

6. Mutating the input maze unintentionally. If the problem says you shouldn't modify the input, use a separate visited set. But when modification is allowed, in-place marking is cleaner and saves space.

Solutions#

Python#

from collections import deque
 
class Solution:
    def nearestExit(self, maze: list[list[str]], entrance: list[int]) -> int:
        R, C = len(maze), len(maze[0])   # grid dimensions
        er, ec = entrance                  # entrance row and column
 
        # BFS queue stores (row, col, steps_taken)
        q = deque([(er, ec, 0)])
 
        # Mark entrance as visited immediately so it isn't treated as exit
        maze[er][ec] = '+'
 
        while q:
            r, c, dist = q.popleft()      # expand current cell
 
            # Explore all 4 directions
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = r + dr, c + dc
 
                # Skip if out of bounds or already visited (wall)
                if not (0 <= nr < R and 0 <= nc < C):
                    continue
                if maze[nr][nc] == '+':
                    continue
 
                # If neighbor is on the border, it's a valid exit
                if nr == 0 or nr == R - 1 or nc == 0 or nc == C - 1:
                    return dist + 1       # BFS guarantees this is minimum steps
 
                # Otherwise mark visited and enqueue
                maze[nr][nc] = '+'        # in-place visited marking
                q.append((nr, nc, dist + 1))
 
        return -1  # no exit reachable

JavaScript#

/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function(maze, entrance) {
    const R = maze.length;              // number of rows
    const C = maze[0].length;           // number of columns
    const [er, ec] = entrance;          // entrance coordinates
 
    // BFS queue: each entry is [row, col, steps]
    const q = [[er, ec, 0]];
    let head = 0;                       // pointer for O(1) dequeue from array
 
    // Mark entrance visited immediately — it is NOT a valid exit
    maze[er][ec] = '+';
 
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];  // 4-directional movement
 
    while (head < q.length) {
        const [r, c, dist] = q[head++]; // dequeue front element
 
        for (const [dr, dc] of dirs) {
            const nr = r + dr;
            const nc = c + dc;
 
            // Skip out-of-bounds or walls
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (maze[nr][nc] === '+') continue;
 
            // Border cell = valid exit (entrance already marked as visited)
            if (nr === 0 || nr === R - 1 || nc === 0 || nc === C - 1) {
                return dist + 1;        // minimum steps by BFS guarantee
            }
 
            // Mark visited and enqueue
            maze[nr][nc] = '+';
            q.push([nr, nc, dist + 1]);
        }
    }
 
    return -1;  // no reachable exit found
};

Complexity Analysis#

• Time: Each cell is visited at most once. In the worst case all m * n cells are processed.
• Space: The BFS queue holds at most the cells on the current frontier. For a grid, the maximum frontier width is bounded by min(m, n) in practice, though in the worst case it could hold O(m * n) cells.

Follow-up Questions#

1. Multiple entrances: If there were multiple starting points, how would you adapt? Use multi-source BFS: enqueue all entrances at step 0.

2. Multiple exits, find all: Return all exits at the minimum distance. Collect all border cells reached at the same BFS level.

3. Weighted moves: If moving right costs 2 and moving down costs 1, BFS no longer works. What algorithm would you use? Dijkstra's algorithm with a min-heap.

4. Dynamic walls: If walls can appear and disappear, how would you handle re-querying? You'd need to invalidate and re-run BFS, or use more advanced techniques like D* Lite.

This Pattern Solves#

• LC 994 — Rotting Oranges — BFS from multiple sources, count levels
• LC 286 — Walls and Gates — multi-source BFS to fill distances
• LC 542 — 01 Matrix — BFS from all zeros to find distance to nearest zero
• LC 1293 — Shortest Path in Grid with Obstacles Elimination — BFS with state = (row, col, remaining eliminations)

Key Takeaways#

• BFS from the entrance; return the current distance the moment you reach any border empty cell that is not the entrance
• Mark the entrance as visited immediately before BFS — cleanest way to exclude it without special-case logic in the loop
• An exit is defined as a border cell (row 0, last row, col 0, or last col) that is empty and not the entrance itself
• BFS guarantees the first exit found is at minimum distance — no need to track all exits
• Time O(mn), space O(mn) — each cell visited at most once
• Check bounds AND wall status before enqueuing — walls block movement
• Return -1 only after the queue is exhausted — if BFS finishes without finding an exit, no path exists