Skip to main content
Talentd

Nearest Exit from Entrance in Maze - Solution & Explanation

MediumArrayBreadth-First SearchMatrix30 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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 == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] is either '.' or '+'.
  • entrance.length == 2
  • 0 <= entrancerow < m
  • 0 <= entrancecol < n
  • entrance will always be an empty cell.

Approach Overview

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 1: Breadth-First Search (BFS) Approach

In this approach, we use the Breadth-First Search (BFS) algorithm to explore the maze. BFS is suitable because it explores nodes layer by layer, ensuring that the shortest path is found. We initialize a queue with the entrance cell and explore its neighbors (up, down, left, right). If a neighbor is an unvisited empty cell and is on the boundary (except the entrance), it can be considered as an exit.

Each time we explore a cell, we mark it as visited by changing its state to '+'. This prevents revisiting nodes, which ensures that we won't traverse the same path multiple times. We keep track of steps taken from the entrance to the current cell, and if we reach an exit, we return the number of steps. If the queue is exhausted without finding an exit, we return -1.

This implementation uses a queue to facilitate the BFS. It starts by enqueuing the entrance and marking it as visited by changing it to '+'. Four possible movement directions are considered (right, down, left, up). As each cell is processed, its unvisited neighbors are enqueued. If a neighbor is a border cell but not the entrance, it is considered the closest exit, and the steps taken are returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the maze. In the worst case, all cells are traversed.
Space Complexity: O(m * n) for the queue used in BFS.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) Approach

In this approach, we use the Depth-First Search (DFS) algorithm to explore the maze. DFS might not be as efficient as BFS for finding the shortest path, but for educational purposes, it demonstrates another way to traverse the maze. We recursively explore each path, marking cells as visited and backtracking when dead-ends or exits are encountered.

This approach keeps a global minimum step count, updating it whenever an exit (that isn't the entrance) is found. Through recursive calls, each possible path is explored until all directions are exhausted. The main objective is to identify the closest exit with respect to steps taken from the entrance cell.

This C implementation of DFS explores each cell using recursive function calls. Directions are processed one by one, checking validity and boundary conditions for a potential exit. Dead-ends lead to recursive backtracking, unmarking visited cells to ensure every path combination is checked. The shortest path's steps are stored in a global variable, updated when an exit is found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((m * n)^2) in the worst case, where m and n are dimensions of the maze.
Space Complexity: O(m * n) due to recursion stack usage in deep recursive path exploration.

Try this approach in the editor →

Approach 3: BFS

We can start from the entrance and perform a breadth-first search (BFS). Each time we reach a new empty cell, we mark it as visited and add it to the queue until we find an empty cell on the boundary, then return the number of steps.

Specifically, we define a queue q, initially adding entrance to the queue. We define a variable ans to record the number of steps, initially set to 1. Then we start the BFS. In each round, we take out all elements from the queue and traverse them. For each element, we try to move in four directions. If the new position is an empty cell, we add it to the queue and mark it as visited. If the new position is an empty cell on the boundary, we return ans. If the queue is empty, we return -1. After this round of search, we increment ans by one and continue to the next round of search.

If we finish the traversal without finding an empty cell on the boundary, we return -1.

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the maze, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) Approach

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the maze. In the worst case, all cells are traversed.
Space Complexity: O(m * n) for the queue used in BFS.

Depth-First Search (DFS) Approach

Time Complexity: O((m * n)^2) in the worst case, where m and n are dimensions of the maze.
Space Complexity: O(m * n) due to recursion stack usage in deep recursive path exploration.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Nearest Exit from Entrance in Maze -(Samsung) : Explanation ➕ Live Coding • codestorywithMIK • 18,461 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nearest Exit from Entrance in Maze easy or hard?
Nearest Exit from Entrance in Maze is rated Medium difficulty on LeetCode. The challenge lies in recognizing it as a shortest-path problem in a grid and correctly handling boundary conditions so the entrance itself is not counted as an exit.
Nearest Exit from Entrance in Maze Python/Java solution
Most implementations use BFS with a queue. Python solutions typically use collections.deque, while Java implementations rely on ArrayDeque or LinkedList. The logic remains the same: enqueue the entrance, expand neighbors, mark visited cells, and stop when the first valid boundary exit is reached.
How to solve Nearest Exit from Entrance in Maze in O(n)?
Treat the maze as a grid graph and run BFS starting from the entrance. Push the entrance into a queue, expand in four directions, and mark cells as visited. As soon as BFS reaches a boundary cell that is not the entrance, return the current distance. Since each cell is processed once, the complexity is O(m*n).
What is the best approach for Nearest Exit from Entrance in Maze?
Breadth-First Search (BFS) is the best approach because the problem asks for the minimum number of steps in an unweighted grid. BFS explores cells level by level, guaranteeing that the first exit reached is the closest one. The algorithm processes each cell at most once, giving O(m*n) time complexity.
Is Nearest Exit from Entrance in Maze asked at Google/Amazon/Meta?
Maze traversal and shortest-path grid problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often involve BFS in grids, finding shortest paths, or escaping mazes. Recognizing BFS as the correct strategy is a common evaluation point.
What data structure is used in Nearest Exit from Entrance in Maze?
The core data structure is a queue used by the Breadth-First Search algorithm. The queue stores cells along with their distance from the entrance. A visited set or in-place marking is also used to prevent revisiting cells in the grid.
What is the time complexity of Nearest Exit from Entrance in Maze?
The optimal BFS solution runs in O(m*n) time where m and n are the maze dimensions. Each cell is visited at most once and each visit checks up to four neighbors. The space complexity is also O(m*n) due to the queue and visited tracking.

Ready to solve this problem?

Practice Nearest Exit from Entrance in Maze with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays