Nearest Exit from Entrance in Maze solution and explanation
Google
9 more videos on this problem
Nearest Exit from Entrance in Maze -(Samsung) : Explanation ➕ Live CodingcodestorywithMIK · 18:45 · 18K views
Leetcode 1926 Nearest Exit from Entrance in Maze | Coding Decoded SDE SheetCoding Decoded · 9:08 · 5K views
Nearest Exit from Entrance in Maze - LeetCode 1926 - Python #leetcode #leetcode75 #bfsDeepti Talesra · 11:07 · 3K views
1926. Nearest Exit from Entrance in Maze (Leetcode Medium)Programming Live with Larry · 8:31 · 3K views
LEETCODE BIWEEKLY CONTEST 56 | PROBLEM 1925 , 1926, 1927 | LEETCODE | CODE EXPLAIENRcode Explainer · 19:31 · 2K views
💻Solving All LeetCode Problems with PYTHON 🐍 - 1926 Nearest Exit from Entrance in MazeAlex Brou · 23:47 · 1K views
1926. Nearest Exit from Entrance in Maze | JavaScript | Breadth First Search | LeetCode DailyLeetCodeWithMonu · 19:01 · 690 views
Leetcode 1926 Nearest Exit from Entrance in Maze | Python BFSEric Websmith · 1:39 · 352 views
LeetCode 1926 – Nearest Exit from Entrance in Maze | C++ BFSLAN Academy · 4:16 · 330 views
Nearest Exit from Entrance in Maze LeetCode - JavaCode with Katie · 13:53 · 224 views
The problem
You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
Example 1:
Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: 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 Explanation: 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 Explanation: There are no exits in this maze.
Constraints:
maze.length == mmaze[i].length == n1 <= m, n <= 100maze[i][j]is either'.'or'+'.entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrancewill always be an empty cell.
Approach overview
Problem Overview: You are given a 2D maze with walls ('+') and empty cells ('.'). Starting from an entrance cell, you must find the minimum number of steps required to reach the nearest exit. An exit is any empty cell on the maze boundary except the entrance itself.
Approach 1: Breadth-First Search (BFS) (Time: O(m*n), Space: O(m*n))
This problem reduces to finding the shortest path in an unweighted grid. Breadth-First Search works perfectly because it explores cells level by level. Start from the entrance, push it into a queue, and expand in four directions (up, down, left, right). Mark visited cells to avoid revisiting. The first time BFS reaches a boundary cell that is not the entrance, you have found the nearest exit. Each cell is processed at most once, so the total work is proportional to the number of cells in the grid.
The key insight: BFS guarantees the shortest path in an unweighted graph. A maze grid is simply a graph where each open cell connects to its neighbors. As soon as you pop a boundary cell from the queue, its distance from the entrance is the minimum number of steps required.
Approach 2: Depth-First Search (DFS) (Time: O(m*n), Space: O(m*n))
A Depth-First Search approach explores all possible paths recursively while tracking the current distance from the entrance. Each recursive call moves to one of the four directions if the cell is within bounds, not a wall, and not visited. When DFS reaches a boundary cell that is not the entrance, update the minimum steps found so far.
DFS works but is less efficient for shortest-path problems in grids because it explores deep paths before discovering shorter ones. You must track visited cells and backtrack correctly. In dense mazes this leads to unnecessary exploration compared to BFS.
The maze itself is a classic matrix traversal problem where each cell can be treated as a node in a graph.
Recommended for interviews: The BFS solution is the expected answer. Interviewers want to see that you recognize the problem as a shortest-path search in an unweighted grid. DFS demonstrates basic traversal knowledge, but BFS shows stronger algorithmic judgment because it naturally guarantees the minimum number of steps.
Approach 1: Breadth-First Search (BFS) Approach
In this approach, we use the Breadth-First Search (BFS) algorithm to explore the maze. BFS is suitable because it explores nodes layer by layer, ensuring that the shortest path is found. We initialize a queue with the entrance cell and explore its neighbors (up, down, left, right). If a neighbor is an unvisited empty cell and is on the boundary (except the entrance), it can be considered as an exit.
Each time we explore a cell, we mark it as visited by changing its state to '+'. This prevents revisiting nodes, which ensures that we won't traverse the same path multiple times. We keep track of steps taken from the entrance to the current cell, and if we reach an exit, we return the number of steps. If the queue is exhausted without finding an exit, we return -1.
from collections import deque
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
m, n = len(maze), len(maze[0])
queue = deque([tuple(entrance)])
maze[entrance[0]][entrance[1]] = '+'
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
steps = 0
while queue:
steps += 1
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.':
if nx == 0 or ny == 0 or nx == m - 1 or ny == n - 1:
return steps
maze[nx][ny] = '+'
queue.append((nx, ny))
return -1import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int m = maze.length, n = maze[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{entrance[0], entrance[1]});
maze[entrance[0]][entrance[1]] = '+';
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
steps++;
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] d : directions) {
int nx = cell[0] + d[0], ny = cell[1] + d[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] == '.') {
if (nx == 0 || ny == 0 || nx == m - 1 || ny == n - 1) {
return steps;
}
maze[nx][ny] = '+';
queue.add(new int[]{nx, ny});
}
}
}
}
return -1;
}
}#include <vector>
#include <queue>
#include <utility>
using namespace std;
class Solution {
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size(), n = maze[0].size();
queue<pair<int, int>> q;
q.push({entrance[0], entrance[1]});
maze[entrance[0]][entrance[1]] = '+';
int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int steps = 0;
while (!q.empty()) {
int q_size = q.size();
steps++;
for (int i = 0; i < q_size; ++i) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + directions[d][0];
int ny = y + directions[d][1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] == '.') {
if (nx == 0 || ny == 0 || nx == m - 1 || ny == n - 1) {
return steps;
}
maze[nx][ny] = '+';
q.push({nx, ny});
}
}
}
}
return -1;
}
};var nearestExit = function(maze, entrance) {
const m = maze.length, n = maze[0].length;
const queue = [[entrance[0], entrance[1]]];
maze[entrance[0]][entrance[1]] = '+';
const directions = [[0,1],[1,0],[0,-1],[-1,0]];
let steps = 0;
while (queue.length) {
steps++;
const size = queue.length;
for (let i = 0; i < size; i++) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] === '.') {
if (nx === 0 || ny === 0 || nx === m - 1 || ny === n - 1) {
return steps;
}
maze[nx][ny] = '+';
queue.push([nx, ny]);
}
}
}
}
return -1;
};#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DIRECTIONS 4
int nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize) {
int directions[DIRECTIONS][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int m = mazeSize, n = mazeColSize[0];
int queue[m*n][2];
int front = 0, rear = 0;
queue[rear][0] = entrance[0];
queue[rear++][1] = entrance[1];
maze[entrance[0]][entrance[1]] = '+';
int steps = 0;
while (front != rear) {
int q_size = rear - front;
steps++;
while (q_size--) {
int x = queue[front][0];
int y = queue[front++][1];
for (int d = 0; d < DIRECTIONS; d++) {
int nx = x + directions[d][0];
int ny = y + directions[d][1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] == '.') {
// check if it's an exit
if (nx == 0 || ny == 0 || nx == m - 1 || ny == n - 1) {
return steps;
}
maze[nx][ny] = '+'; // mark as visited
queue[rear][0] = nx;
queue[rear++][1] = ny;
}
}
}
}
return -1;
}using System;
using System.Collections.Generic;
public class Solution {
public int NearestExit(char[][] maze, int[] entrance) {
int m = maze.Length, n = maze[0].Length;
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(new int[] { entrance[0], entrance[1] });
maze[entrance[0]][entrance[1]] = '+';
int[][] directions = new int[4][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
int steps = 0;
while (queue.Count > 0) {
steps++;
int size = queue.Count;
for (int i = 0; i < size; i++) {
int[] cell = queue.Dequeue();
foreach (var d in directions) {
int nx = cell[0] + d[0], ny = cell[1] + d[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] == '.') {
if (nx == 0 || ny == 0 || nx == m - 1 || ny == n - 1) {
return steps;
}
maze[nx][ny] = '+';
queue.Enqueue(new int[] { nx, ny });
}
}
}
}
return -1;
}
}In this Python solution, the BFS is implemented using a deque for the queue operations. The entrance is first enqueued and marked as visited. The algorithm iteratively processes each cell, checking for the nearest exit. If no exit is found by the time all possible paths are explored, it returns -1.
Time Complexity: O(m * n). Similar to other languages, due to the grid traversal.
Space Complexity: O(m * n). The deque holds all cells potentially.
Approach 2: Depth-First Search (DFS) Approach
In this approach, we use the Depth-First Search (DFS) algorithm to explore the maze. DFS might not be as efficient as BFS for finding the shortest path, but for educational purposes, it demonstrates another way to traverse the maze. We recursively explore each path, marking cells as visited and backtracking when dead-ends or exits are encountered.
This approach keeps a global minimum step count, updating it whenever an exit (that isn't the entrance) is found. Through recursive calls, each possible path is explored until all directions are exhausted. The main objective is to identify the closest exit with respect to steps taken from the entrance cell.
class Solution:
def __init__(self):
self.min_steps = float('inf')
self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def dfs(self, maze, x, y, steps):
m, n = len(maze), len(maze[0])
if x < 0 or y < 0 or x >= m or y >= n or maze[x][y] != '.':
return
if (x == 0 or y == 0 or x == m - 1 or y == n - 1) and steps != 0:
self.min_steps = min(self.min_steps, steps)
maze[x][y] = '+' # mark as visited
for dx, dy in self.directions:
self.dfs(maze, x + dx, y + dy, steps + 1)
maze[x][y] = '.' # backtrack
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
self.dfs(maze, entrance[0], entrance[1], 0)
return -1 if self.min_steps == float('inf') else self.min_stepsimport java.util.Arrays;
class Solution {
int minSteps = Integer.MAX_VALUE;
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
public void dfs(char[][] maze, int x, int y, int steps) {
int m = maze.length, n = maze[0].length;
if (x < 0 || y < 0 || x >= m || y >= n || maze[x][y] != '.') return;
if ((x == 0 || y == 0 || x == m - 1 || y == n - 1) && steps != 0) {
minSteps = Math.min(minSteps, steps);
}
maze[x][y] = '+'; // mark as visited
for (int[] d : directions) {
dfs(maze, x + d[0], y + d[1], steps + 1);
}
maze[x][y] = '.'; // backtrack
}
public int nearestExit(char[][] maze, int[] entrance) {
dfs(maze, entrance[0], entrance[1], 0);
return minSteps == Integer.MAX_VALUE ? -1 : minSteps;
}
}#include <vector>
#include <climits>
using namespace std;
void dfs(vector<vector<char>>& maze, int x, int y, int steps, int &minSteps) {
static vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int m = maze.size(), n = maze[0].size();
if (x < 0 || y < 0 || x >= m || y >= n || maze[x][y] != '.') return;
if ((x == 0 || y == 0 || x == m - 1 || y == n - 1) && steps != 0) {
minSteps = min(minSteps, steps);
}
maze[x][y] = '+'; // mark as visited
for (auto& d : directions) {
int nx = x + d[0], ny = y + d[1];
dfs(maze, nx, ny, steps + 1, minSteps);
}
maze[x][y] = '.'; // backtrack
}
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int minSteps = INT_MAX;
dfs(maze, entrance[0], entrance[1], 0, minSteps);
return (minSteps == INT_MAX) ? -1 : minSteps;
}var nearestExit = function(maze, entrance) {
let minSteps = Infinity;
const directions = [[0,1],[1,0],[0,-1],[-1,0]];
function dfs(x, y, steps) {
const m = maze.length, n = maze[0].length;
if (x < 0 || y < 0 || x >= m || y >= n || maze[x][y] !== '.') return;
if ((x === 0 || y === 0 || x === m - 1 || y === n - 1) && steps !== 0) {
minSteps = Math.min(minSteps, steps);
}
maze[x][y] = '+'; // mark as visited
for (const [dx, dy] of directions) {
dfs(x + dx, y + dy, steps + 1);
}
maze[x][y] = '.'; // backtrack
}
dfs(entrance[0], entrance[1], 0);
return minSteps === Infinity ? -1 : minSteps;
};#include <stdbool.h>
#include <limits.h>
int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
void dfs(char** maze, int m, int n, int x, int y, int steps, int* minSteps) {
if (x < 0 || y < 0 || x >= m || y >= n || maze[x][y] != '.') {
return;
}
if ((x == 0 || y == 0 || x == m - 1 || y == n - 1) && steps != 0 && steps < *minSteps) {
*minSteps = steps;
}
maze[x][y] = '+'; // mark as visited
for (int d = 0; d < 4; d++) {
int nx = x + directions[d][0];
int ny = y + directions[d][1];
dfs(maze, m, n, nx, ny, steps + 1, minSteps);
}
maze[x][y] = '.'; // backtrack
}
int nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize) {
int m = mazeSize, n = mazeColSize[0];
int minSteps = INT_MAX;
dfs(maze, m, n, entrance[0], entrance[1], 0, &minSteps);
return (minSteps == INT_MAX) ? -1 : minSteps;
}using System;
public class Solution {
private int minSteps = int.MaxValue;
private int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
public int NearestExit(char[][] maze, int[] entrance) {
DFS(maze, entrance[0], entrance[1], 0);
return minSteps == int.MaxValue ? -1 : minSteps;
}
private void DFS(char[][] maze, int x, int y, int steps) {
int m = maze.Length, n = maze[0].Length;
if (x < 0 || y < 0 || x >= m || y >= n || maze[x][y] != '.') return;
if ((x == 0 || y == 0 || x == m - 1 || y == n - 1) && steps != 0) {
minSteps = Math.Min(minSteps, steps);
}
maze[x][y] = '+'; // mark as visited
foreach (var d in directions) {
DFS(maze, x + d[0], y + d[1], steps + 1);
}
maze[x][y] = '.'; // backtrack
}
}The Python solution employs DFS to handle grid searching recursively. For each cell, potential exits are pursued with a counter tracking steps. Backtracking through recursive methods permits exploring all unique paths and ensuring a valid and shortest exit route is logged.
Time Complexity: O((m * n)^2), owing to potential exhaustive path checks.
Space Complexity: O(m * n), based on recursion depth usage.
Approach 3: 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.
Specifically, we define a queue q, initially adding entrance to the queue. We define a variable ans to record the number of steps, initially set to 1. Then we start the BFS. In each round, we take out all elements from the queue and traverse them. For each element, we try to move in four directions. If the new position is an empty cell, we add it to the queue and mark it as visited. If the new position is an empty cell on the boundary, we return ans. If the queue is empty, we return -1. After this round of search, we increment ans by one and continue to the next round of search.
If we finish the traversal without finding an empty cell on the boundary, we return -1.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the maze, respectively.
function nearestExit(maze: string[][], entrance: number[]): number {
const dir = [0, 1, 0, -1, 0];
const q = [[...entrance, 0]];
maze[entrance[0]][entrance[1]] = '+';
for (const [i, j, ans] of q) {
for (let d = 0; d < 4; d++) {
const [x, y] = [i + dir[d], j + dir[d + 1]];
const v = maze[x]?.[y];
if (!v && ans) {
return ans;
}
if (v === '.') {
q.push([x, y, ans + 1]);
maze[x][y] = '+';
}
}
}
return -1;
}func nearestExit(maze [][]byte, entrance []int) int {
m, n := len(maze), len(maze[0])
q := [][2]int{{entrance[0], entrance[1]}}
maze[entrance[0]][entrance[1]] = '+'
dirs := []int{-1, 0, 1, 0, -1}
for ans := 1; len(q) > 0; ans++ {
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
for l := 0; l < 4; l++ {
x, y := p[0]+dirs[l], p[1]+dirs[l+1]
if x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' {
if x == 0 || x == m-1 || y == 0 || y == n-1 {
return ans
}
q = append(q, [2]int{x, y})
maze[x][y] = '+'
}
}
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(m * n). Similar to other languages, due to the grid traversal. |
| Depth-First Search (DFS) Approach | Time Complexity: O((m * n)^2), owing to potential exhaustive path checks. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Best choice for shortest path in an unweighted grid or maze |
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Useful for exploring all paths or practicing recursive grid traversal |
Frequently asked questions
Is Nearest Exit from Entrance in Maze easy or hard?
Nearest Exit from Entrance in Maze is rated Medium difficulty on LeetCode. The challenge lies in recognizing it as a shortest-path problem in a grid and correctly handling boundary conditions so the entrance itself is not counted as an exit.
Nearest Exit from Entrance in Maze Python/Java solution
Most implementations use BFS with a queue. Python solutions typically use collections.deque, while Java implementations rely on ArrayDeque or LinkedList. The logic remains the same: enqueue the entrance, expand neighbors, mark visited cells, and stop when the first valid boundary exit is reached.
How to solve Nearest Exit from Entrance in Maze in O(n)?
Treat the maze as a grid graph and run BFS starting from the entrance. Push the entrance into a queue, expand in four directions, and mark cells as visited. As soon as BFS reaches a boundary cell that is not the entrance, return the current distance. Since each cell is processed once, the complexity is O(m*n).
What is the best approach for Nearest Exit from Entrance in Maze?
Breadth-First Search (BFS) is the best approach because the problem asks for the minimum number of steps in an unweighted grid. BFS explores cells level by level, guaranteeing that the first exit reached is the closest one. The algorithm processes each cell at most once, giving O(m*n) time complexity.
Is Nearest Exit from Entrance in Maze asked at Google/Amazon/Meta?
Maze traversal and shortest-path grid problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often involve BFS in grids, finding shortest paths, or escaping mazes. Recognizing BFS as the correct strategy is a common evaluation point.
What data structure is used in Nearest Exit from Entrance in Maze?
The core data structure is a queue used by the Breadth-First Search algorithm. The queue stores cells along with their distance from the entrance. A visited set or in-place marking is also used to prevent revisiting cells in the grid.
What is the time complexity of Nearest Exit from Entrance in Maze?
The optimal BFS solution runs in O(m*n) time where m and n are the maze dimensions. Each cell is visited at most once and each visit checks up to four neighbors. The space complexity is also O(m*n) due to the queue and visited tracking.