Nearest Exit from Entrance in Maze

Nearest Exit from Entrance in Maze

What is this problem about?

The Nearest Exit from Entrance in Maze problem places you at a given entrance cell in a grid-based maze where '.' means open space and '+' means a wall. Find the nearest exit — an open cell on the boundary of the grid that is not the entrance itself. Return the minimum number of steps to reach it, or -1 if unreachable. This Nearest Exit from Entrance in Maze coding problem is a standard BFS shortest-path problem on a grid.

Why is this asked in interviews?

Samsung, Uber, Microsoft, Meta, Amazon, and Google ask this because it's a clean test of BFS on a 2D grid with exit condition checking. It validates that candidates know BFS gives the shortest path in unweighted graphs, can implement grid BFS correctly, and can check boundary conditions for exits. The array, matrix, and BFS interview pattern is the core.

Algorithmic pattern used

BFS from entrance. Initialize the queue with the entrance. For each cell dequeued, explore all 4 neighbors. If a neighbor is an open cell ('.') not yet visited: check if it's on the boundary — if yes, return the current step count. Otherwise, add it to the queue with step count + 1. If the queue empties without finding an exit, return -1.

Example explanation

Maze (4×4):

+ + + +
. . . +
+ + . +
. . . +

Entrance: (1,0). BFS expands: (1,0)→step 0. Neighbors: (1,1) step 1. From (1,1): (1,2) step 2, (2,1)... blocked. (1,2): (2,2) step 3. (2,2): (3,2) step 4 — (3,2) is on bottom boundary → return 4.

Common mistakes candidates make

• Using DFS (finds a path but not necessarily the shortest).
• Not marking cells as visited (infinite loop).
• Counting the entrance as an exit (must exclude the starting cell).
• Not checking all four boundary conditions (top row, bottom row, leftmost column, rightmost column).

Interview preparation tip

BFS on grids is a fundamental pattern. The exit condition here — "open cell on the boundary, not the entrance" — is checked as soon as a cell is dequeued or enqueued (checking on enqueue is more efficient). Practice all BFS grid variants: shortest path to any target cell, flood fill, number of islands. Getting BFS right on the first try — correct visited marking, boundary checks, and step counting — is the clearest signal of strong algorithm foundations.