LeetCode 1926 - Nearest Exit from Entrance in Maze

The problem gives us a rectangular maze represented by a 2D grid. Each cell contains either: - '.', meaning the cell is empty and can be walked on - '+', meaning the cell is a wall and cannot be crossed We are also given the coordinates of an entrance cell.

leetcodemediumarraybreadth-first-searchmatrix

LeetCode Problem 1926

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem gives us a rectangular maze represented by a 2D grid. Each cell contains either:

  • '.', meaning the cell is empty and can be walked on
  • '+', meaning the cell is a wall and cannot be crossed

We are also given the coordinates of an entrance cell. The entrance is guaranteed to be an empty cell.

From any cell, we may move in four directions:

  • Up
  • Down
  • Left
  • Right

Each move costs exactly one step.

The goal is to find the minimum number of steps required to reach the nearest exit. An exit is defined as:

  1. An empty cell
  2. Located on the border of the maze
  3. Not equal to the entrance cell itself

If no reachable exit exists, we return -1.

The important detail is that the entrance does not count as an exit, even if it lies on the border. This condition is a common source of bugs.

The constraints are relatively small:

  • 1 <= m, n <= 100

This means the maze contains at most 10,000 cells. Since this is not extremely large, graph traversal algorithms such as Breadth-First Search are very feasible.

Conceptually, the maze forms an unweighted graph:

  • Each empty cell is a node
  • Adjacent empty cells are connected by edges
  • Every move has equal cost

Because every move costs exactly one step, the shortest path problem naturally suggests Breadth-First Search.

Several edge cases are important:

  • The entrance may already lie on the border, but it still cannot be treated as an exit.
  • There may be no exits at all.
  • There may be exits that are unreachable because walls block the path.
  • The maze may consist of only one cell.
  • Multiple exits may exist, and we must return the closest one.

Approaches

Brute Force Approach

A brute force strategy would be:

  1. Identify every valid exit in the maze.
  2. For each exit, run a separate search from the entrance to determine the shortest path length.
  3. Return the minimum reachable distance.

This works because eventually every exit is checked, and the shortest reachable one is selected.

However, this approach is inefficient because we repeatedly traverse the maze for every exit. In the worst case, the maze could contain many border cells, and each search could visit nearly all cells.

If there are E exits and m * n cells, the complexity becomes roughly:

  • O(E * m * n)

Since E can itself be proportional to m + n, this becomes unnecessarily expensive.

Optimal Approach

The key observation is that all moves have equal cost.

Whenever we need the shortest number of moves in an unweighted graph, Breadth-First Search is the ideal tool.

Breadth-First Search explores cells level by level:

  • First all cells at distance 1
  • Then all cells at distance 2
  • Then all cells at distance 3
  • And so on

Therefore, the first exit encountered during BFS must be the nearest exit.

Instead of searching separately for every exit, we start one BFS from the entrance and stop immediately when we encounter the first valid exit.

This guarantees optimality while visiting each cell at most once.

Approach Time Complexity Space Complexity Notes
Brute Force O(E × m × n) O(m × n) Runs a search for every possible exit
Optimal O(m × n) O(m × n) Single BFS traversal finds nearest exit immediately

Algorithm Walkthrough

Step 1: Initialize BFS Structures

We create:

  • A queue for BFS traversal
  • A visited structure to avoid revisiting cells

The queue stores:

  • Current row
  • Current column
  • Distance from the entrance

We begin by inserting the entrance with distance 0.

Step 2: Mark the Entrance as Visited

We immediately mark the entrance as visited.

This prevents revisiting it later and avoids infinite loops.

Step 3: Define the Four Directions

We define movement vectors for:

  • Up
  • Down
  • Left
  • Right

This simplifies neighbor traversal.

Step 4: Process the Queue

While the queue is not empty:

  1. Remove the front cell
  2. Explore all four neighboring cells

For each neighbor:

  • Check bounds
  • Ensure it is not a wall
  • Ensure it has not already been visited

If valid:

  • Mark it visited
  • Compute its distance
  • Add it to the queue

Step 5: Detect an Exit

After moving to a valid neighboring cell, check whether:

  • It lies on the border
  • It is not the entrance

If both conditions hold, we immediately return the current distance plus one.

Because BFS explores in increasing distance order, this is guaranteed to be the nearest exit.

Step 6: Handle No Reachable Exit

If BFS completes without finding any exit, return -1.

Why it works

Breadth-First Search explores nodes in strictly increasing order of distance from the starting point.

This means:

  • Every cell reached earlier has a shorter or equal path length than cells reached later.
  • The first exit discovered must therefore be the closest exit.

The visited set ensures each cell is processed at most once, preventing cycles and redundant work.

Python Solution

from collections import deque
from typing import List

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows = len(maze)
        cols = len(maze[0])

        start_row, start_col = entrance

        queue = deque()
        queue.append((start_row, start_col, 0))

        visited = set()
        visited.add((start_row, start_col))

        directions = [
            (-1, 0),  # up
            (1, 0),   # down
            (0, -1),  # left
            (0, 1)    # right
        ]

        while queue:
            row, col, steps = queue.popleft()

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                # Check boundaries
                if (
                    new_row < 0
                    or new_row >= rows
                    or new_col < 0
                    or new_col >= cols
                ):
                    continue

                # Skip walls
                if maze[new_row][new_col] == '+':
                    continue

                # Skip visited cells
                if (new_row, new_col) in visited:
                    continue

                # Check whether this cell is an exit
                is_border = (
                    new_row == 0
                    or new_row == rows - 1
                    or new_col == 0
                    or new_col == cols - 1
                )

                if is_border:
                    return steps + 1

                visited.add((new_row, new_col))
                queue.append((new_row, new_col, steps + 1))

        return -1

The implementation begins by determining the maze dimensions and extracting the entrance coordinates.

A deque is used because BFS repeatedly removes elements from the front and appends new elements to the back. Both operations are efficient with a deque.

The visited set prevents revisiting cells. Without it, the search could repeatedly cycle between cells, causing unnecessary work or infinite loops.

Each queue element stores:

  • Row index
  • Column index
  • Current distance from the entrance

Inside the BFS loop, we examine all four neighbors of the current cell.

We skip neighbors that:

  • Fall outside the maze
  • Are walls
  • Were already visited

For every valid unvisited empty cell, we check whether it lies on the border. If it does, we immediately return the path length because BFS guarantees this is the shortest path.

If BFS finishes without finding an exit, the function returns -1.

Go Solution

package main

func nearestExit(maze [][]byte, entrance []int) int {
	rows := len(maze)
	cols := len(maze[0])

	type State struct {
		row   int
		col   int
		steps int
	}

	queue := []State{
		{entrance[0], entrance[1], 0},
	}

	visited := make([][]bool, rows)
	for i := 0; i < rows; i++ {
		visited[i] = make([]bool, cols)
	}

	visited[entrance[0]][entrance[1]] = true

	directions := [][]int{
		{-1, 0},
		{1, 0},
		{0, -1},
		{0, 1},
	}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, dir := range directions {
			newRow := current.row + dir[0]
			newCol := current.col + dir[1]

			// Boundary check
			if newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols {
				continue
			}

			// Wall check
			if maze[newRow][newCol] == '+' {
				continue
			}

			// Visited check
			if visited[newRow][newCol] {
				continue
			}

			isBorder := (
				newRow == 0 ||
				newRow == rows-1 ||
				newCol == 0 ||
				newCol == cols-1
			)

			if isBorder {
				return current.steps + 1
			}

			visited[newRow][newCol] = true

			queue = append(queue, State{
				newRow,
				newCol,
				current.steps + 1,
			})
		}
	}

	return -1
}

The Go implementation follows exactly the same BFS logic as the Python solution.

Instead of Python tuples, Go uses a State struct to store:

  • Row
  • Column
  • Step count

The visited structure is implemented using a 2D boolean slice instead of a hash set, which is efficient because the maze dimensions are known in advance.

Go slices naturally support queue behavior by removing the first element using:

queue = queue[1:]

No integer overflow concerns exist here because the maximum path length is bounded by the number of cells, which is at most 10,000.

Worked Examples

Example 1

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

entrance = [1,2]

Initial queue:

Queue Visited
[(1,2,0)] {(1,2)}

Process (1,2):

Possible moves:

  • Up → (0,2) valid and on border
  • Down → blocked
  • Left → (1,1) valid
  • Right → blocked

Since (0,2) is a border cell and not the entrance, return:

1

Example 2

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

entrance = [1,0]

Initial state:

Queue Visited
[(1,0,0)] {(1,0)}

Process (1,0):

Neighbors:

  • (1,1) valid

Queue becomes:

Queue
[(1,1,1)]

Process (1,1):

Neighbors:

  • (1,2) valid and on border

Return:

2

Example 3

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

The entrance lies on the border, but it does not count as an exit.

No other empty cells exist.

BFS ends immediately.

Return:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Each cell is visited at most once
Space O(m × n) Queue and visited structure may store all cells

The BFS traversal processes each reachable cell once. Every neighbor check is constant time, so the total runtime is proportional to the number of cells in the maze.

The queue and visited structures can both grow to contain every cell in the worst case, giving linear auxiliary space usage.

Test Cases

from typing import List

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        from collections import deque

        rows = len(maze)
        cols = len(maze[0])

        queue = deque([(entrance[0], entrance[1], 0)])
        visited = {(entrance[0], entrance[1])}

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            row, col, steps = queue.popleft()

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue

                if maze[nr][nc] == '+':
                    continue

                if (nr, nc) in visited:
                    continue

                if nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1:
                    return steps + 1

                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))

        return -1

sol = Solution()

# Example 1
assert sol.nearestExit(
    [["+", "+", ".", "+"],
     [".", ".", ".", "+"],
     ["+", "+", "+", "."]],
    [1, 2]
) == 1  # nearest exit directly above

# Example 2
assert sol.nearestExit(
    [["+", "+", "+"],
     [".", ".", "."],
     ["+", "+", "+"]],
    [1, 0]
) == 2  # entrance on border does not count

# Example 3
assert sol.nearestExit(
    [[".", "+"]],
    [0, 0]
) == -1  # no exits exist

# Single cell maze
assert sol.nearestExit(
    [["."]],
    [0, 0]
) == -1  # entrance is only cell

# Exit reachable in one move
assert sol.nearestExit(
    [["+", "."],
     [".", "."]],
    [1, 1]
) == 1  # border exit adjacent

# Multiple exits, choose nearest
assert sol.nearestExit(
    [[".", ".", "."],
     [".", "+", "."],
     [".", ".", "."]],
    [1, 0]
) == 1  # nearest border exit

# Completely blocked maze
assert sol.nearestExit(
    [["+", "+", "+"],
     ["+", ".", "+"],
     ["+", "+", "+"]],
    [1, 1]
) == -1  # surrounded by walls

# Larger maze with winding path
assert sol.nearestExit(
    [[".", "+", ".", ".", "."],
     [".", "+", ".", "+", "."],
     [".", ".", ".", "+", "."],
     ["+", "+", "+", "+", "."],
     [".", ".", ".", ".", "."]],
    [2, 2]
) == 2  # shortest exit path

print("All tests passed!")
Test Why
Example 1 Verifies standard BFS shortest path
Example 2 Ensures entrance is not treated as exit
Example 3 Verifies no-exit scenario
Single cell maze Smallest possible input
Adjacent exit Verifies immediate neighbor detection
Multiple exits Ensures nearest exit is selected
Completely blocked maze Verifies unreachable handling
Larger winding maze Tests more complex traversal

Edge Cases

Entrance on the Border

One of the most important edge cases occurs when the entrance itself lies on the maze boundary.

A naive implementation might immediately return 0, incorrectly treating the entrance as an exit.

The problem explicitly states that the entrance does not count as an exit. Our implementation handles this correctly because it only checks newly visited neighboring cells for exit status. The entrance itself is never evaluated as a candidate exit.

Maze With No Valid Exit

Another important case is when no reachable border cell exists.

This can happen because:

  • All border cells are walls
  • Paths are blocked by walls
  • The maze contains only the entrance

In this situation, BFS eventually exhausts all reachable cells and the queue becomes empty. The algorithm then correctly returns -1.

Cycles and Revisiting Cells

Open mazes may contain loops where the same cell can be reached through multiple paths.

Without a visited structure, BFS could repeatedly revisit the same cells, causing excessive work or infinite loops.

The implementation prevents this by marking cells visited immediately when they are added to the queue. This guarantees every cell is processed at most once.

Single Row or Single Column Mazes

Very narrow mazes can expose indexing mistakes and border condition bugs.

For example:

[[".", ".", "."]]

Every cell lies on the border.

The implementation safely handles these cases because border detection uses straightforward row and column comparisons that remain valid regardless of maze dimensions.