Nearest Exit from Entrance in Maze – LeetCode75 Python Solution Explained

The Nearest Exit from Entrance in Maze problem (LeetCode75) is a grid traversal problem that tests your understanding of BFS, shortest path algorithms, and maze navigation. It is a common coding interview question because it evaluates your ability to traverse a 2D grid efficiently while managing visited cells.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given a m x n maze represented as a 2D character array, where:

• "." represents an empty cell you can walk through.
• "+" represents a wall you cannot pass.

You are also given the coordinates of an entrance cell [entrance_row, entrance_col].

Return the minimum number of steps to reach the nearest exit, where an exit is any empty cell at the boundary of the maze excluding the entrance. If no exit exists, return -1.

Example 1

Input:

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

Output:

1

Explanation:

• Starting at [1,2], the nearest exit is [0,2].
• Only 1 step is required.

Example 2

Input:

maze = [["+", "+", "+"],
        [".", ".", "."],
        ["+", "+", "+"]]
entrance = [1,0]

Output:

2

Example 3

Input:

maze = [[".", "+"]]
entrance = [0,0]

Output:

-1

Complete Python Solution

from collections import deque
from typing import List

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows, cols = len(maze), len(maze[0])
        entrance_row, entrance_col = entrance
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Right, Left, Down, Up

        queue = deque([(entrance_row, entrance_col, 0)])
        visited = set([(entrance_row, entrance_col)])

        while queue:
            current_row, current_col, steps = queue.popleft()

            # Check if we reached an exit (boundary excluding entrance)
            if (
                (current_row, current_col) != (entrance_row, entrance_col)
                and (current_row == 0 or current_row == rows - 1 
                     or current_col == 0 or current_col == cols - 1)
            ):
                return steps

            # Explore all four directions
            for dr, dc in directions:
                new_row, new_col = current_row + dr, current_col + dc

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and maze[new_row][new_col] == "."
                    and (new_row, new_col) not in visited
                ):
                    visited.add((new_row, new_col))
                    queue.append((new_row, new_col, steps + 1))

        return -1  # No exit found

Step-by-Step Explanation

Step 1: Initialize BFS

Use a queue to perform Breadth-First Search (BFS) from the entrance cell. Keep track of visited cells to prevent cycles.

queue = deque([(entrance_row, entrance_col, 0)])
visited = set([(entrance_row, entrance_col)])

• Each queue element stores (row, col, steps).

Step 2: Process Queue

While the queue is not empty, pop the front cell and check if it is an exit.

current_row, current_col, steps = queue.popleft()

if (current_row, current_col) != (entrance_row, entrance_col) and (
    current_row == 0 or current_row == rows - 1
    or current_col == 0 or current_col == cols - 1
):
    return steps

• Exit is any boundary cell not equal to entrance.

Step 3: Explore All Four Directions

For each direction (up, down, left, right), calculate the next cell. If it is within bounds, open and not visited, add it to the queue.

for dr, dc in directions:
    new_row, new_col = current_row + dr, current_col + dc

    if 0 <= new_row < rows and 0 <= new_col < cols and maze[new_row][new_col] == "." and (new_row, new_col) not in visited:
        visited.add((new_row, new_col))
        queue.append((new_row, new_col, steps + 1))

Step 4: Return Result

If the queue is empty and no exit is found, return -1.

return -1

Time and Space Complexity

• Time Complexity:O(m * n)
  • Every cell is visited at most once.
• Space Complexity:O(m * n)
  • BFS queue and visited set may store all empty cells.

Edge Cases

1. Entrance is on the boundary: Do not count as exit.
2. Maze fully blocked by walls: Return -1.
3. Multiple paths: BFS ensures shortest path is found.
4. Single cell maze: Return -1 if no exit.

Real-World Applications

• Robot Navigation: Finding the shortest path to exit a maze-like environment.
• Game Development: Pathfinding for characters in grid-based maps.
• Emergency Evacuation Plans: Determine nearest exit in building layouts.
• Network Routing: BFS can model shortest path in network topologies.

Conclusion

The Nearest Exit from Entrance in Maze problem is an excellent example of BFS traversal in 2D grids. By exploring level by level, BFS guarantees the shortest path to the exit.

This problem improves your skills in queue management, grid traversal and shortest-path computation, which are crucial for coding interviews and real-world applications in robotics, gaming and network routing.

Related Reads

• Keys and Rooms – LeetCode75 Python Solution Explained
• Smallest Number in Infinite Set – LeetCode75 Python Solution Explained
• Maximum Subsequence Score – LeetCode75 Python Solution Explained
• Search in a Binary Search Tree – LeetCode75 Python Solution Explained
• Maximum Level Sum of a Binary Tree – LeetCode75 Python Solution Explained

References

1. LeetCode – Nearest Exit from Entrance in Maze
2. BFS Algorithm – GeeksforGeeks
3. Shortest Path in a Grid