Watch 10 video solutions for Nearest Exit from Entrance in Maze, a medium level problem involving Array, Breadth-First Search, Matrix. This walkthrough by codestorywithMIK has 16,152 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
Example 1:
Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away.
Example 2:
Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] Output: 2 Explanation: There is 1 exit in this maze at [1,2]. [1,0] does not count as an exit since it is the entrance cell. Initially, you are at the entrance cell [1,0]. - You can reach [1,2] by moving 2 steps right. Thus, the nearest exit is [1,2], which is 2 steps away.
Example 3:
Input: maze = [[".","+"]], entrance = [0,0] Output: -1 Explanation: There are no exits in this maze.
Constraints:
maze.length == mmaze[i].length == n1 <= m, n <= 100maze[i][j] is either '.' or '+'.entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrance will always be an empty cell.Problem Overview: You are given a 2D maze with walls ('+') and empty cells ('.'). Starting from an entrance cell, you must find the minimum number of steps required to reach the nearest exit. An exit is any empty cell on the maze boundary except the entrance itself.
Approach 1: Breadth-First Search (BFS) (Time: O(m*n), Space: O(m*n))
This problem reduces to finding the shortest path in an unweighted grid. Breadth-First Search works perfectly because it explores cells level by level. Start from the entrance, push it into a queue, and expand in four directions (up, down, left, right). Mark visited cells to avoid revisiting. The first time BFS reaches a boundary cell that is not the entrance, you have found the nearest exit. Each cell is processed at most once, so the total work is proportional to the number of cells in the grid.
The key insight: BFS guarantees the shortest path in an unweighted graph. A maze grid is simply a graph where each open cell connects to its neighbors. As soon as you pop a boundary cell from the queue, its distance from the entrance is the minimum number of steps required.
Approach 2: Depth-First Search (DFS) (Time: O(m*n), Space: O(m*n))
A Depth-First Search approach explores all possible paths recursively while tracking the current distance from the entrance. Each recursive call moves to one of the four directions if the cell is within bounds, not a wall, and not visited. When DFS reaches a boundary cell that is not the entrance, update the minimum steps found so far.
DFS works but is less efficient for shortest-path problems in grids because it explores deep paths before discovering shorter ones. You must track visited cells and backtrack correctly. In dense mazes this leads to unnecessary exploration compared to BFS.
The maze itself is a classic matrix traversal problem where each cell can be treated as a node in a graph.
Recommended for interviews: The BFS solution is the expected answer. Interviewers want to see that you recognize the problem as a shortest-path search in an unweighted grid. DFS demonstrates basic traversal knowledge, but BFS shows stronger algorithmic judgment because it naturally guarantees the minimum number of steps.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Best choice for shortest path in an unweighted grid or maze |
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Useful for exploring all paths or practicing recursive grid traversal |