#1926

Medium

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Nearest Exit from Entrance in Maze

Find the shortest path from the maze entrance to the nearest border exit using BFS over a 2D array matrix efficiently.

Problem Statement

You are given an m x n 2D maze represented by a matrix where empty cells are '.', walls are '+', and an entrance position [entrancerow, entrancecol] indicates your starting point. From the entrance, you can move one cell at a time up, down, left, or right without crossing walls or leaving the maze.

An exit is any empty cell located at the border of the maze, excluding the entrance itself. Return the minimum number of steps to reach the nearest exit, or -1 if no exit is reachable. Each step counts as moving to an adjacent cell in one of the four directions.

Examples

Example 1

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]

Output: 1

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

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

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.

Solution Approach

Breadth-First Search Traversal

Implement BFS starting from the entrance, enqueuing each empty neighboring cell while marking visited positions. BFS ensures that the first exit found is at the minimal distance from the entrance.

Boundary Exit Check

At each BFS level, check if the current cell is on the maze boundary and not the entrance. If so, immediately return the current distance as the shortest path to the nearest exit.

Avoid Revisiting Cells

Mark visited cells as you enqueue them or temporarily convert them to walls. This prevents cycles, reduces unnecessary traversal, and ensures BFS discovers the shortest path correctly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) because each cell is visited at most once during BFS. Space complexity is O(m n) for the queue and visited markers, proportional to the maze size.

What Interviewers Usually Probe

They may ask about edge cases where the entrance is on the boundary.
Expect discussion on why BFS guarantees the shortest path compared to DFS.
Be ready to explain how marking visited cells prevents infinite loops in the traversal.

Common Pitfalls or Variants

Common pitfalls

Treating the entrance as an exit accidentally when it is on the border.
Forgetting to check bounds before accessing neighboring cells.
Using DFS which may find a longer path and fail on minimal steps requirement.

Follow-up variants

Find the longest path from entrance to any exit using BFS levels differently.
Return all exits reachable with the minimum number of steps.
Modify the maze to include weighted steps and use BFS with priority queue.

FAQ

What is the optimal approach to solve Nearest Exit from Entrance in Maze?

Breadth-First Search over the 2D array is optimal because it finds the shortest path to the nearest exit efficiently.

Can DFS be used instead of BFS for this maze problem?

DFS can explore paths but may not guarantee the nearest exit is found first, making BFS preferable for minimal steps.

How do I handle the entrance if it is on the maze boundary?

Do not count the entrance as an exit; only other empty boundary cells qualify as exits.

What is the time and space complexity for the BFS solution?

Both time and space complexity are O(m*n) since each cell is visited at most once and stored in the queue.

Which traversal type is recommended for array plus BFS problems?

Level-order traversal in BFS is recommended for array plus BFS patterns to find minimal distances from a starting point.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        i, j = entrance
        q = deque([(i, j)])
        maze[i][j] = "+"
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n and maze[x][y] == ".":
                        if x == 0 or x == m - 1 or y == 0 or y == n - 1:
                            return ans
                        q.append((x, y))
                        maze[x][y] = "+"
        return -1

Continue Practicing

#1905 count sub islands #1970 last day where you can still cross #1992 find all groups of farmland