Nearest Exit Maze LeetCode 1926 Guide

LeetCode 1926 — Nearest Exit from Entrance in Maze — gives you an m x n maze represented as a grid of characters. A '+' cell is a wall you cannot enter. A '.' cell is empty and walkable. You are also given the entrance as a coordinate [row, col], which is guaranteed to be an empty cell. Your task: find the shortest path from the entrance to any exit cell, returning the number of steps, or -1 if no exit exists.

An exit is defined as any empty cell ('.') that sits on the boundary of the grid — row 0, row m-1, col 0, or col n-1 — that is NOT the entrance itself. Even if the entrance happens to be on the boundary, it does not count as an exit. You must reach a different boundary cell. Movement is allowed in four directions: up, down, left, right. You cannot move diagonally or step into wall cells.

The problem belongs to the classic BFS-on-a-grid family. The grid is unweighted — every step costs one unit — so BFS from the entrance gives the shortest path directly. The first time BFS reaches a boundary empty cell that is not the entrance, that distance is the answer.

BFS is the algorithm of choice for finding shortest paths in unweighted grids. When all edge weights are equal (every step costs 1), BFS explores cells in order of increasing distance from the source. The first time it reaches any target cell, it has found the shortest possible path to that cell. No other algorithm is needed.

Starting BFS from the entrance, cells at distance 1 are processed first, then distance 2, and so on. The moment any cell at distance d is a boundary empty cell other than the entrance, we return d immediately. There is no need to continue — BFS guarantees this is the minimum number of steps. If the queue empties without finding an exit, return -1.

This contrasts with DFS, which explores deep paths first and cannot guarantee it finds the shortest path without exhaustive search. For shortest-path problems on unweighted grids, always reach for BFS. The implementation uses a deque for O(1) enqueue and dequeue, and marks cells visited immediately upon enqueuing to prevent duplicate processing.

The implementation starts by enqueuing the entrance at distance 0 and immediately marking it visited by setting maze[entrance[0]][entrance[1]] = '+'. This in-place mutation avoids a separate visited set and ensures the entrance is never re-processed or incorrectly identified as an exit during BFS. Each queue entry holds (row, col, steps).

In each iteration, dequeue the front cell and expand its four neighbors. For each neighbor, check bounds and that the cell is '.'. If the neighbor is on the boundary (row 0, row m-1, col 0, or col n-1), return steps + 1 immediately — it is the nearest exit. Otherwise, mark the neighbor visited by setting it to '+' and enqueue it with steps + 1.

If the queue empties without finding a boundary cell, return -1. The boundary check on neighbors (not on the dequeued cell itself) ensures the entrance is correctly excluded: the entrance is marked visited before BFS begins, so it is never enqueued as a neighbor. The neighbor check fires for the first boundary cell reached, which BFS guarantees is the closest.

A cell qualifies as an exit if it satisfies two conditions simultaneously: it must be on the grid boundary, and it must not be the entrance. The boundary condition is: row == 0 OR row == m-1 OR col == 0 OR col == n-1. This covers all four edges of the grid. Interior cells can never be exits regardless of how many steps it takes to reach them.

The entrance exclusion is handled automatically by marking the entrance visited before BFS begins. Since visited cells are set to '+', the entrance will never appear as an empty neighbor during BFS expansion. You do not need to explicitly check 'is this cell the entrance?' during neighbor evaluation — the visited mark handles it.

Exit detection happens when checking neighbors, not when processing a dequeued cell. When a neighbor satisfies both the boundary condition and the emptiness condition, BFS returns steps + 1 immediately. This is correct because BFS processes cells in order of distance, so the first qualifying boundary cell encountered is the closest one.

Consider a 3x3 maze: [["+",".","+"],[".",".","+"],["+",".","+"]]. The entrance is at [1,2] — row 1, col 2. BFS starts: enqueue (1,2,0), mark (1,2) visited. Level 0 dequeued: (1,2). Neighbors: (0,2) is '+' skip; (2,2) is '+' skip; (1,1) is '.' interior — enqueue (1,1,1), mark visited; (1,3) out of bounds skip. Queue: [(1,1,1)].

Level 1 dequeued: (1,1). Neighbors: (0,1) is '.' — row 0 is boundary! Return 1+1 = 2. The nearest exit is at (0,1) reached in 2 steps. BFS correctly found the shortest path without exploring further. The walls at (0,0), (0,2), (2,0), (2,2) were never relevant since the path through (1,1) to (0,1) was found first.

For a maze where the entrance has no path to any boundary exit — for example, if the entrance is fully surrounded by walls — the queue empties after processing the entrance with no neighbors enqueued, and the function returns -1. This edge case is handled naturally without special-casing: an empty queue after BFS always means no exit was reachable.

Python BFS solution: from collections import deque. def nearestExit(maze, entrance): m, r = len(maze), len(maze[0]); er, ec = entrance; maze[er][ec] = '+'; q = deque([(er, ec, 0)]); while q: row, col, steps = q.popleft(); for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = row+dr, col+dc; if 0<=nr<m and 0<=nc<r and maze[nr][nc]=='.': if nr==0 or nr==m-1 or nc==0 or nc==r-1: return steps+1; maze[nr][nc]='+'; q.append((nr,nc,steps+1)); return -1. Time O(m*n), space O(m*n) for the queue.

Java BFS solution: public int nearestExit(char[][] maze, int[] entrance) { int m=maze.length, n=maze[0].length; int er=entrance[0], ec=entrance[1]; maze[er][ec]='+'; Queue<int[]> q=new LinkedList<>(); q.offer(new int[]{er,ec,0}); int[][] dirs={{-1,0},{1,0},{0,-1},{0,1}}; while(!q.isEmpty()){ int[] cur=q.poll(); int row=cur[0],col=cur[1],steps=cur[2]; for(int[] d:dirs){ int nr=row+d[0],nc=col+d[1]; if(nr>=0&&nr<m&&nc>=0&&nc<n&&maze[nr][nc]=='.'){ if(nr==0||nr==m-1||nc==0||nc==n-1) return steps+1; maze[nr][nc]='+'; q.offer(new int[]{nr,nc,steps+1}); } } } return -1; }

Both implementations mutate the maze in-place to mark visited cells, avoiding a separate boolean visited array. This is acceptable when the input maze is not needed after the function returns, which is the case in most interview settings. If in-place mutation is not allowed, use a Set<String> or boolean[][] visited array initialized to false, and check/set visited instead of checking/setting maze cells.

Shortest Path in Binary Matrix (LeetCode 1091) is structurally identical: BFS from the top-left corner to the bottom-right corner of a binary grid, counting steps. Walls are 1-cells, empty cells are 0-cells. The same BFS template applies — enqueue source, expand 8-directional neighbors, mark visited, return distance when target is reached. Nearest Exit from Entrance in Maze is the boundary-exit variant of this pattern.

Rotting Oranges (LeetCode 994) uses multi-source BFS from all initially rotten oranges simultaneously. The core BFS mechanism is the same — expand level by level, mark visited, count levels — but the source is a set of cells rather than a single entrance. Understanding Nearest Exit from Entrance in Maze solidifies the single-source BFS pattern that multi-source BFS builds on.

Walls and Gates (LeetCode 286) reverses the direction: instead of finding the nearest gate from each cell individually, it runs multi-source BFS from all gates simultaneously and fills in distances. Open the Lock (LeetCode 752) applies BFS to an abstract state space rather than a 2D grid, but the same shortest-path reasoning applies. Mastering grid BFS with Nearest Exit transfers directly to all these related problems.