What is the brute force approach and complexity for Nearest Exit from Entrance in Maze?

Walk every simple path from the entrance; keep the shortest one that reaches an exit with time complexity O(3^(m · n)) and space complexity O(m · n).

What is the optimal approach and complexity for Nearest Exit from Entrance in Maze?

BFS by distance from the entrance; the first border cell popped is the nearest exit with optimal time complexity O(m · n) and space complexity O(m · n).

How do you identify the pattern for Nearest Exit from Entrance in Maze?

Look for key signals in the prompt: "steps from the entrance" indicates Every move costs the same, so the distance is the number of moves. A BFS gives the shortest distance to every cell.; "nearest exit" indicates Stop at the first exit found in distance order, not at any exit the search happens to reach.; "empty cells and walls in a grid" indicates The grid is a graph: each empty cell is a node and each move is an edge..

Nearest Exit from Entrance in Maze

Medium·LeetCode #1926Basic Anchor

LeetCode

Jump:

30-Second Mental ModelGraph BFS → Grid shortest path (BFS from one source)

Complexity:O(3^(m · n))→O(m · n)

Key Insight

Run a breadth-first search from the entrance. It visits cells in rings of equal distance: all cells 1 step away, then all cells 2 steps away, and so on. The first border cell it pops is the nearest exit, so the search can stop there.

Core Validity Invariant

A cell is popped only after every cell that is closer to the entrance, so the first border cell popped is the nearest exit. The entrance is 0 steps away and is never counted.

Problem

You are given a maze as a grid. Each cell is an empty cell (.) or a wall (+). You are also given the entrance, an empty cell where you start.

In one step you can move up, down, left or right into an empty cell. An exit is an empty cell on the border of the maze. The entrance does not count as an exit, even when it sits on the border.

Return the number of steps to the nearest exit, or -1 if no exit can be reached.

Input

maze, an m × n grid of . and +, and entrance = [row, col], an empty cell.

Output

The number of steps to the nearest reachable exit, or -1 if there is none.

Example 1

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

Output: 1

The exit at [0, 2] is one step up from the entrance. The other exits are farther away, or walled off.

Example 2

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

Output: 2

The entrance is on the left border, but it is not an exit. The only exit is [1, 2], two steps to the right.

Example 3

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

Output: -1

There is no exit. The only other cell is a wall.

Constraints

• 1 ≤ m, n ≤ 100
• Each cell is `.` (empty) or `+` (wall).
• The entrance is always an empty cell.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is the answer the length of any path to an exit, or the length of the shortest one?
2.
If I try all four directions from the entrance at the same time, which border cell can I reach first?
3.
Does the entrance count as an exit when it sits on the border?
4.
If a depth-first search finds an exit, is that exit guaranteed to be the nearest one?
5.
After k rounds of a search, which cells are known to be exactly k steps away?

Brute force approach

Idea

Walk every path that starts at the entrance and never reuses a cell. Stop a path when it reaches a border cell, and keep the smallest step count seen. Every path is walked, so the shortest one cannot be missed. The number of paths grows exponentially with the grid.

Thinking process

1
The answer is the smallest number of moves over all paths that end on a border cell.
2
A path may not step on the same cell twice. So the search marks each cell while the path stands on it, and unmarks it when it backtracks.
3
Check on the 4 × 4 maze .++. / +... / ++.. / .... with the entrance at (1,1). From (1,1) the only open move is right to (1,2). From there the search tries down first: (2,2), then (3,2), a border cell 3 moves away, so it records 3. It backtracks and tries (2,3), another exit at 3 moves. Then it backtracks to (1,2) and tries (1,3), a border cell 2 moves away. That becomes the new best.
4
Only after every path is tried is the smallest recorded value the answer. If no exit is ever reached, the answer is -1.

Visual

Blue = on the current path, purple = best exit so far, orange = an exit that was not shorter. Each step is one move, one exit, or one backtrack.

Brute force: try every path, keep the shortestmaze = [".++.", "+...", "++..", "...."], entrance = [1, 1]step 1/15

maze

.cur

State

moves on path: 0
best so far: —
exits reached: 0

path

(1,1)

Start at the entrance (1,1)

The brute force starts at the entrance and tries each neighbour in turn: up, down, left, right. A cell on the current path is never entered again.

Code & Implementation

brute.cpp

class Solution {
    // Tries every simple path from (r, c). steps = moves made so far.
    void go(vector<vector<char>>& maze, int r, int c, int steps, vector<vector<bool>>& onPath, int& best) {
        int m = maze.size(), n = maze[0].size();
        // An exit is a border cell reached by walking. The entrance (steps == 0) is not one.
        if (steps > 0 && (r == 0 || c == 0 || r == m - 1 || c == n - 1)) {
            best = min(best, steps);
            return;   // walking on past an exit only makes the path longer
        }
        const int dr[] = {-1, 1, 0, 0};
        const int dc[] = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
            if (maze[nr][nc] != '.' || onPath[nr][nc]) continue;
            onPath[nr][nc] = true;      // this path now stands on the cell
            go(maze, nr, nc, steps + 1, onPath, best);
            onPath[nr][nc] = false;     // undo, so other paths can use it
        }
    }

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> onPath(m, vector<bool>(n, false));
        onPath[entrance[0]][entrance[1]] = true;
        int best = INT_MAX;
        go(maze, entrance[0], entrance[1], 0, onPath, best);
        return best == INT_MAX ? -1 : best;
    }
};

import java.util.*;

class Solution {
    // Tries every simple path from (r, c). steps = moves made so far.
    private void go(char[][] maze, int r, int c, int steps, boolean[][] onPath, int[] best) {
        int m = maze.length, n = maze[0].length;
        // An exit is a border cell reached by walking. The entrance (steps == 0) is not one.
        if (steps > 0 && (r == 0 || c == 0 || r == m - 1 || c == n - 1)) {
            best[0] = Math.min(best[0], steps);
            return;   // walking on past an exit only makes the path longer
        }
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
            if (maze[nr][nc] != '.' || onPath[nr][nc]) continue;
            onPath[nr][nc] = true;      // this path now stands on the cell
            go(maze, nr, nc, steps + 1, onPath, best);
            onPath[nr][nc] = false;     // undo, so other paths can use it
        }
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        boolean[][] onPath = new boolean[m][n];
        onPath[entrance[0]][entrance[1]] = true;
        int[] best = new int[]{Integer.MAX_VALUE};
        go(maze, entrance[0], entrance[1], 0, onPath, best);
        return best[0] == Integer.MAX_VALUE ? -1 : best[0];
    }
}

from typing import List

class Solution:
    # Tries every simple path from (r, c). steps = moves made so far.
    def go(self, maze: List[List[str]], r: int, c: int, steps: int, on_path: List[List[bool]], best: List[float]) -> None:
        m, n = len(maze), len(maze[0])
        # An exit is a border cell reached by walking. The entrance (steps == 0) is not one.
        if steps > 0 and (r == 0 or c == 0 or r == m - 1 or c == n - 1):
            best[0] = min(best[0], float(steps))
            return   # walking on past an exit only makes the path longer

        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]
            if nr < 0 or nc < 0 or nr >= m or nc >= n:
                continue
            if maze[nr][nc] != '.' or on_path[nr][nc]:
                continue
            on_path[nr][nc] = True      # this path now stands on the cell
            self.go(maze, nr, nc, steps + 1, on_path, best)
            on_path[nr][nc] = False     # undo, so other paths can use it

    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        on_path = [[False] * n for _ in range(m)]
        on_path[entrance[0]][entrance[1]] = True
        best = [float('inf')]
        self.go(maze, entrance[0], entrance[1], 0, on_path, best)
        return -1 if best[0] == float('inf') else int(best[0])

export function nearestExit(maze: string[][], entrance: number[]): number {
    const m = maze.length;
    const n = maze[0].length;
    const onPath: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
    onPath[entrance[0]][entrance[1]] = true;
    let best = Infinity;

    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];

    // Tries every simple path from (r, c). steps = moves made so far.
    function go(r: number, c: number, steps: number): void {
        // An exit is a border cell reached by walking. The entrance (steps == 0) is not one.
        if (steps > 0 && (r === 0 || c === 0 || r === m - 1 || c === n - 1)) {
            best = Math.min(best, steps);
            return;   // walking on past an exit only makes the path longer
        }
        for (let d = 0; d < 4; d++) {
            const nr = r + dr[d];
            const nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
            if (maze[nr][nc] !== '.' || onPath[nr][nc]) continue;
            onPath[nr][nc] = true;      // this path now stands on the cell
            go(nr, nc, steps + 1);
            onPath[nr][nc] = false;     // undo, so other paths can use it
        }
    }

    go(entrance[0], entrance[1], 0);
    return best === Infinity ? -1 : best;
}

Complexity

Time O(3^(m · n))Space O(m · n)

After the first step, each move has at most three choices, because the cell it came from is marked. A simple path has at most m · n cells, so the search makes at most 3^(m · n) calls. The onPath grid takes m · n, and the recursion goes at most m · n deep. Only usable for tiny mazes.

Optimized approach

Idea

Start from brute force

Brute force tries every path and then keeps the shortest. Most of those paths reach the same cells again and again, and most are longer than a path already found.

Find the repeated work

Two different paths can reach the same cell. Brute force explores everything beyond that cell again for each path. A BFS explores each cell once, from the arrival that is closest.

Define the state — what variables do I need?

queue: Cells waiting to be popped, in order of distance from the entrance.
seen: Cells already pushed. A cell is pushed at most once.
steps: The distance shared by every cell in the layer being popped.

Define validity

A cell is popped only after every cell that is closer to the entrance, so the first border cell popped is the nearest exit. The entrance is 0 steps away and is never counted.

Define the transitions — when does each pointer move, and why is it safe?

Start

Push the entrance, mark it seen, steps = 0

It is the only cell at distance 0.

Pop a cell on the border, and steps > 0

Return steps

Every cell closer than this has already been popped, and none of them was an exit.

Each open neighbour that is not seen yet

Mark it seen and push it, one more step away

This first arrival is the shortest one, so later arrivals never need to be kept.

Queue empty

Return -1

Every reachable cell has been visited, and none was a border cell.

What does the current window add to the answer?

Each popped cell is tested once for being a border exit. The first one found ends the search, because nothing closer can be an exit.

Code & Implementation

optimal.cpp

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        const int dr[] = {-1, 1, 0, 0};
        const int dc[] = {0, 0, -1, 1};

        // Each pass of the loop is one more step away from the entrance.
        vector<vector<bool>> seen(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({entrance[0], entrance[1]});
        seen[entrance[0]][entrance[1]] = true;   // marked when pushed, so each cell enters once

        for (int steps = 0; !q.empty(); steps++) {
            int layer = q.size();               // only the cells at distance `steps`
            for (int i = 0; i < layer; i++) {
                auto [r, c] = q.front();
                q.pop();
                // The entrance is at 0 steps, so it is not an exit.
                if (steps > 0 && (r == 0 || c == 0 || r == m - 1 || c == n - 1)) return steps;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                    if (maze[nr][nc] != '.' || seen[nr][nc]) continue;
                    seen[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
        return -1;   // no border cell is reachable
    }
};

import java.util.*;

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        // Each pass of the loop is one more step away from the entrance.
        boolean[][] seen = new boolean[m][n];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{entrance[0], entrance[1]});
        seen[entrance[0]][entrance[1]] = true;   // marked when pushed, so each cell enters once

        for (int steps = 0; !q.isEmpty(); steps++) {
            int layer = q.size();               // only the cells at distance `steps`
            for (int i = 0; i < layer; i++) {
                int[] cell = q.poll();
                int r = cell[0], c = cell[1];
                // The entrance is at 0 steps, so it is not an exit.
                if (steps > 0 && (r == 0 || c == 0 || r == m - 1 || c == n - 1)) return steps;
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                    if (maze[nr][nc] != '.' || seen[nr][nc]) continue;
                    seen[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return -1;   // no border cell is reachable
    }
}

from typing import List
from collections import deque

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]

        # Each pass of the loop is one more step away from the entrance.
        seen = [[False] * n for _ in range(m)]
        q = deque([(entrance[0], entrance[1])])
        seen[entrance[0]][entrance[1]] = True   # marked when pushed, so each cell enters once

        steps = 0
        while q:
            layer = len(q)                      # only the cells at distance `steps`
            for _ in range(layer):
                r, c = q.popleft()
                # The entrance is at 0 steps, so it is not an exit.
                if steps > 0 and (r == 0 or c == 0 or r == m - 1 or c == n - 1):
                    return steps
                for d in range(4):
                    nr, nc = r + dr[d], c + dc[d]
                    if nr < 0 or nc < 0 or nr >= m or nc >= n:
                        continue
                    if maze[nr][nc] != '.' or seen[nr][nc]:
                        continue
                    seen[nr][nc] = True
                    q.append((nr, nc))
            steps += 1

        return -1   # no border cell is reachable

export function nearestExit(maze: string[][], entrance: number[]): number {
    const m = maze.length;
    const n = maze[0].length;
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];

    // Each pass of the loop is one more step away from the entrance.
    const seen: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
    const q: [number, number][] = [[entrance[0], entrance[1]]];
    seen[entrance[0]][entrance[1]] = true;   // marked when pushed, so each cell enters once

    let head = 0;
    for (let steps = 0; head < q.length; steps++) {
        const layer = q.length - head;              // only the cells at distance `steps`
        for (let i = 0; i < layer; i++) {
            const [r, c] = q[head++];
            // The entrance is at 0 steps, so it is not an exit.
            if (steps > 0 && (r === 0 || c === 0 || r === m - 1 || c === n - 1)) return steps;
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                if (maze[nr][nc] !== '.' || seen[nr][nc]) continue;
                seen[nr][nc] = true;
                q.push([nr, nc]);
            }
        }
    }
    return -1;   // no border cell is reachable
}

Complexity

Time O(m · n)Space O(m · n)

Every cell is pushed at most once, and each pushed cell looks at four neighbours. The seen grid and the queue each hold at most m · n cells.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Walk every simple path from the entrance; keep the shortest one that reaches an exit	O(3^(m · n))	O(m · n)
Optimal	BFS by distance from the entrance; the first border cell popped is the nearest exit	O(m · n)	O(m · n)

Why does this belong to this pattern?

Clues in the problem statement

“steps from the entrance”Every move costs the same, so the distance is the number of moves. A BFS gives the shortest distance to every cell.
“nearest exit”Stop at the first exit found in distance order, not at any exit the search happens to reach.
“empty cells and walls in a grid”The grid is a graph: each empty cell is a node and each move is an edge.

Unweighted grid+shortest number of steps+one source, BFS by distance→Graph BFS → Grid shortest path (BFS from one source)

This is the anchor of the grid-shortest sub-pattern. Every move costs one step, so BFS gives the true distance to every cell. The only twist is the stop rule: the first border cell popped is the answer, not the first one a DFS happens to reach. The next two questions keep the BFS and change what counts as a step or a state.

Don't make this mistake

Counting the entrance as an exit

✗ if (r == 0 || c == 0 || r == m - 1 || c == n - 1) return steps;

✓ if (steps > 0 && (r == 0 || c == 0 || r == m - 1 || c == n - 1)) return steps;

The second example's entrance [1, 0] is on the left border. Without the steps > 0 check the first pop returns 0, but the correct answer is 2. The entrance is never an exit.

Pattern confusion: DFS returns the first exit it finds

✗ // DFS from the entrance; return the steps at the first border cell reached

✓ // BFS by distance; the first border cell popped is the nearest one

On the dry-run maze a DFS that tries up, down, left, right first walks to a border cell 5 steps away. The nearest exit is 3 steps away at (1,4). A depth-first search follows one path to its end, so the first exit it reaches is not the closest.

Forgetting the seen grid

✗ queue.push({nr, nc}); // push every open neighbour, every time

✓ if (seen[nr][nc]) continue; seen[nr][nc] = true; queue.push({nr, nc});

Take the maze ++++ / +..+ / +..+ / ++++ with the entrance at (1,1). The four interior cells form a loop with no border cell in it, so without seen the queue keeps refilling forever and the search never ends. With seen the queue empties and the answer is -1.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Shortest Path in Binary Matrix