Nearest Exit from Entrance in Maze

Medium
1530.

Nearest Exit from Entrance in Maze

Nearest Exit from Entrance in Maze is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Meta interviews.

A maze of m rows and n columns is given as maze, one string per row: '.' is an open cell and '+' is a wall. You stand at the open cell entrance = [row, col].

Each step moves you one cell up, down, left or right; you cannot enter a wall or leave the grid. An exit is any open cell on the outer border of the maze — except the entrance itself.

Return the number of steps on the shortest route from the entrance to the nearest exit, or -1 if no exit can be reached.

Example 1

Input
maze = ["+++++","+...+","+.+.+","+...+","++.++"], entrance = [1,1]
Output
4
Explanation
The only exit is (4,2), reached via (2,1), (3,1) and (3,2).

Example 2

Input
maze = ["+.+","...","+.+"], entrance = [1,0]
Output
2
Explanation
The entrance lies on the border but does not count; (0,1), (2,1) and (1,2) are each two steps away.

Example 3

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

Constraints

  • maze.length == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] is '.' or '+'
  • entrance.length == 2
  • 0 <= entrance[0] < m
  • 0 <= entrance[1] < n
  • entrance is an open cell
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function(maze, entrance) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Nearest Exit from Entrance in Maze — Problem & Solution

Nearest Exit from Entrance in Maze solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Nearest Exit from Entrance in Maze is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Meta interviews.

Problem statement

A maze of m rows and n columns is given as maze, one string per row: '.' is an open cell and '+' is a wall. You stand at the open cell entrance = [row, col].

Each step moves you one cell up, down, left or right; you cannot enter a wall or leave the grid. An exit is any open cell on the outer border of the maze — except the entrance itself.

Return the number of steps on the shortest route from the entrance to the nearest exit, or -1 if no exit can be reached.

Example 1

Input: maze = ["+++++","+...+","+.+.+","+...+","++.++"], entrance = [1,1]
Output: 4
Explanation: The only exit is (4,2), reached via (2,1), (3,1) and (3,2).

Example 2

Input: maze = ["+.+","...","+.+"], entrance = [1,0]
Output: 2
Explanation: The entrance lies on the border but does not count; (0,1), (2,1) and (1,2) are each two steps away.

Example 3

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

Constraints

  • maze.length == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] is '.' or '+'
  • entrance.length == 2
  • 0 <= entrance[0] < m
  • 0 <= entrance[1] < n
  • entrance is an open cell

Hints for Nearest Exit from Entrance in Maze

  1. Hint 1

    Every step costs the same, so the shortest route is found by breadth-first search.

  2. Hint 2

    Start the BFS at the entrance and mark it visited so it is never mistaken for an exit.

  3. Hint 3

    The first open border cell the BFS discovers is the nearest exit — return its distance immediately.

How to solve Nearest Exit from Entrance in Maze

Breadth-first search from the entrance explores cells in order of distance, so the first border cell it reaches is the nearest exit.

Approach

  1. Mark the entrance visited and push it with distance 0.
  2. Pop a cell; for each of its four neighbours that is inside the grid, open and unvisited:
  3. if the neighbour lies on the border, return the current distance + 1; otherwise mark it and push it with distance + 1.
  4. If the queue runs dry, return -1.

Why it works

BFS dequeues cells in non-decreasing distance order, and each neighbour is discovered at distance (parent + 1), which is its true shortest distance. Checking the exit condition at discovery time therefore returns the minimum over all exits. The entrance is visited from the start, so it can never be reported as an exit even when it sits on the border.

Complexity

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

Pitfalls

  • An entrance on the border is not an exit — a check made when popping the start would wrongly return 0.
  • Mark cells visited when they are pushed, not when popped, or the queue can hold the same cell many times.
  • A 1 × 1 maze has no exit at all.

Reference solution

Python

from typing import List
from collections import deque

def nearestExit(maze: List[str], entrance: List[int]) -> int:
    m, n = len(maze), len(maze[0])
    seen = [[False] * n for _ in range(m)]
    sr, sc = entrance
    seen[sr][sc] = True
    q = deque([(sr, sc, 0)])
    while q:
        r, c, d = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and maze[nr][nc] == '.':
                if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                    return d + 1
                seen[nr][nc] = True
                q.append((nr, nc, d + 1))
    return -1

Java

public static int nearestExit(String[] maze, int[] entrance) {
    int m = maze.length, n = maze[0].length();
    int[] dist = new int[m * n];
    Arrays.fill(dist, -1);
    int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
    int[] queue = new int[m * n];
    int head = 0, tail = 0;
    int start = entrance[0] * n + entrance[1];
    dist[start] = 0;
    queue[tail++] = start;
    while (head < tail) {
        int cur = queue[head++];
        int r = cur / n, c = cur % n;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || maze[nr].charAt(nc) != '.') continue;
            int id = nr * n + nc;
            if (dist[id] != -1) continue;
            dist[id] = dist[cur] + 1;
            if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) return dist[id];
            queue[tail++] = id;
        }
    }
    return -1;
}

C++

int nearestExit(vector<string>& maze, vector<int>& entrance) {
    int m = maze.size(), n = maze[0].size();
    vector<int> dist(m * n, -1);
    int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    int start = entrance[0] * n + entrance[1];
    dist[start] = 0;
    vector<int> queue;
    queue.push_back(start);
    for (size_t h = 0; h < queue.size(); h++) {
        int cur = queue[h];
        int r = cur / n, c = cur % n;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || maze[nr][nc] != '.') continue;
            int id = nr * n + nc;
            if (dist[id] != -1) continue;
            dist[id] = dist[cur] + 1;
            if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) return dist[id];
            queue.push_back(id);
        }
    }
    return -1;
}

JavaScript

var nearestExit = function(maze, entrance) {
    var m = maze.length, n = maze[0].length;
    var dist = [];
    for (var i = 0; i < m * n; i++) dist.push(-1);
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var start = entrance[0] * n + entrance[1];
    dist[start] = 0;
    var queue = [start];
    for (var h = 0; h < queue.length; h++) {
        var r = Math.floor(queue[h] / n), c = queue[h] % n;
        for (var d = 0; d < 4; d++) {
            var nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || maze[nr][nc] !== '.') continue;
            var id = nr * n + nc;
            if (dist[id] !== -1) continue;
            dist[id] = dist[queue[h]] + 1;
            if (nr === 0 || nr === m - 1 || nc === 0 || nc === n - 1) return dist[id];
            queue.push(id);
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal