Nearest Exit from Entrance in Maze
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses Depth-First Search (DFS) to exhaustively explore all possible paths from the entrance. It keeps track of the minimum number of steps required to reach any exit cell. Because DFS explores as deeply as possible along one path before backtracking, it does not guarantee that the first exit found is the nearest one. Therefore, it must potentially explore a vast number of paths to find the true minimum, making it highly inefficient for this problem.
Algorithm
- Initialize a global variable
minStepsto infinity. - Create a
visitedboolean matrix to keep track of cells visited in the current path to avoid cycles. - Define a recursive function
dfs(row, col, steps). - Start the search from the entrance:
dfs(entrance_row, entrance_col, 0). - In the
dfsfunction:- If the current cell is out of bounds, a wall, or already visited in the current path, return.
- If the current path's length (
steps) is already greater than or equal tominSteps, prune this path and return. - If the current cell is an exit (on the border and not the entrance), update
minSteps = min(minSteps, steps). - Mark the current cell as visited.
- Recursively call
dfsfor all four neighbors (up, down, left, right), incrementingsteps. - Backtrack by unmarking the current cell as visited. This is crucial to allow other paths to explore this cell.
- After the initial
dfscall completes, ifminStepsis still infinity, no exit was reachable. Return -1. Otherwise, returnminSteps.
Walkthrough
The core of this method is a recursive function that explores the maze. We maintain a visited array to prevent getting stuck in cycles within a single path exploration. A global variable, minSteps, stores the length of the shortest path found so far.
The search starts at the entrance. For each cell, the function checks if it's a valid move. If the cell is an exit (a border cell that is not the entrance), we compare its path length (steps) with minSteps and update it if the new path is shorter. A key part of this brute-force DFS is backtracking: after exploring from a cell, we must unmark it as visited so that other potential paths can use it. This exhaustive search ensures we check all possibilities but at a very high computational cost.
class Solution { int minSteps = Integer.MAX_VALUE; public int nearestExit(char[][] maze, int[] entrance) { int m = maze.length; int n = maze[0].length; boolean[][] visited = new boolean[m][n]; dfs(entrance[0], entrance[1], 0, maze, visited, entrance); return minSteps == Integer.MAX_VALUE ? -1 : minSteps; } private void dfs(int r, int c, int steps, char[][] maze, boolean[][] visited, int[] entrance) { // Check if out of bounds, a wall, or already visited in the current path if (r < 0 || r >= maze.length || c < 0 || c >= maze[0].length || maze[r][c] == '+' || visited[r][c]) { return; } // Check if it's an exit (and not the entrance cell) boolean isEntrance = (r == entrance[0] && c == entrance[1]); if (!isEntrance && (r == 0 || r == maze.length - 1 || c == 0 || c == maze[0].length - 1)) { minSteps = Math.min(minSteps, steps); // We found an exit, but must continue searching for a potentially shorter path. // Returning here would be incorrect as another path to another exit might be shorter. } // Pruning: if current steps are already not better than the best found so far, stop. if (steps >= minSteps) { return; } visited[r][c] = true; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { dfs(r + dr[i], c + dc[i], steps + 1, maze, visited, entrance); } visited[r][c] = false; // Backtrack to allow other paths to use this cell }}Complexity
Time
O(3^(m*n)) in the worst case. From any given cell, there are at most 3 new directions to explore. The algorithm might explore all simple paths, leading to an exponential runtime.
Space
O(m * n) for the recursion stack in the worst case (a path that visits every cell) and the `visited` matrix.
Trade-offs
Pros
Conceptually simple if familiar with recursion and graph traversal.
Cons
Extremely inefficient for this problem, as it's not designed to find the shortest path directly.
Time complexity can be exponential in the worst case, leading to a 'Time Limit Exceeded' error on larger mazes.
Prone to stack overflow errors for mazes with very long paths due to deep recursion.
This problem asks for the shortest path in a maze where each step has an equal cost, which is a classic use case for Breadth-First Search (BFS). BFS explores the maze layer by layer from the starting point. This guarantees that the first time we reach an exit cell, we have found a path with the minimum number of steps. Any other path to this exit or any other exit would be at least as long.
Algorithm
- Get the maze dimensions
mandn. - Initialize a queue and add the
entrancecoordinates to it. - Mark the
entrancecell as visited to prevent cycles. A common way is to modify the input grid, e.g.,maze[entrance_row][entrance_col] = '+'. - Initialize a
stepscounter to 0. - Start a loop that continues as long as the queue is not empty.
- In each iteration, process all nodes at the current level. Get the
levelSizeof the queue. - Increment
steps. This new value represents the distance to the next level of cells. - Loop
levelSizetimes to process each cell at the current distance.- Dequeue a cell
(r, c). - Explore its four neighbors
(nr, nc). - For each neighbor, check if it's valid (within bounds and not a wall).
- If a valid neighbor is on the border, it's the nearest exit. Return the current
steps. - If a valid neighbor is not an exit, mark it as visited and enqueue it for processing in the next level.
- Dequeue a cell
- If the queue becomes empty and no exit was found, return -1.
Walkthrough
We can model the maze as an unweighted graph where each empty cell is a node and adjacent empty cells are connected by an edge. The BFS algorithm is perfect for finding the shortest path from a single source in such a graph.
We start by placing the entrance cell into a queue. We also need a way to keep track of visited cells to avoid infinite loops and redundant computations; this can be done with a separate boolean[][] array or by modifying the input maze in-place (e.g., changing visited . to +).
The search proceeds in levels. We maintain a steps counter. In each step of the BFS, we dequeue all the cells that are at the current distance (steps - 1) and enqueue all their valid, unvisited neighbors. These new neighbors are at distance steps. Before adding a neighbor to the queue, we check if it's an exit (an empty cell on the border). Since BFS explores level by level, the first exit we encounter is guaranteed to be the nearest one. We can immediately return the current steps count. If the queue becomes empty before an exit is found, it means no exit is reachable.
import java.util.LinkedList;import java.util.Queue; class Solution { public int nearestExit(char[][] maze, int[] entrance) { int m = maze.length; int n = maze[0].length; Queue<int[]> queue = new LinkedList<>(); queue.offer(entrance); // Mark the entrance as visited to avoid revisiting it. // Modifying the input is a common trick to save space. maze[entrance[0]][entrance[1]] = '+'; int steps = 0; int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!queue.isEmpty()) { int levelSize = queue.size(); steps++; for (int i = 0; i < levelSize; i++) { int[] current = queue.poll(); int r = current[0]; int c = current[1]; // Explore neighbors for (int[] dir : dirs) { int newR = r + dir[0]; int newC = c + dir[1]; // Check if the new cell is out of bounds if (newR < 0 || newR >= m || newC < 0 || newC >= n) { continue; } // Check if the new cell is a wall (or already visited) if (maze[newR][newC] == '+') { continue; } // If we found a valid path to a border cell, it's an exit. // Since this is BFS, this is the shortest path. if (newR == 0 || newR == m - 1 || newC == 0 || newC == n - 1) { return steps; } // Mark as visited and add to the queue for the next level maze[newR][newC] = '+'; queue.offer(new int[]{newR, newC}); } } } // If the queue becomes empty, no path to an exit exists. return -1; }}Complexity
Time
O(m * n), where `m` and `n` are the dimensions of the maze. Every empty cell is enqueued and dequeued at most once.
Space
O(m * n) in the worst case. The space is used by the queue, which can hold a number of cells proportional to the width of the maze.
Trade-offs
Pros
Optimal and efficient, as it guarantees finding the shortest path.
Visits each cell at most once, resulting in a linear time complexity.
Cons
Uses extra space for the queue, which can be up to O(m * n) in the worst case.
If the implementation modifies the input grid to mark visited cells, it might be an undesirable side effect.
Solutions
Solution
class Solution {public int nearestExit(char[][] maze, int[] entrance) { int m = maze.length; int n = maze[0].length; Deque<int[]> q = new ArrayDeque<>(); q.offer(entrance); maze[entrance[0]][entrance[1]] = '+'; int ans = 0; int[] dirs = {-1, 0, 1, 0, -1}; while (!q.isEmpty()) { ++ans; for (int k = q.size(); k > 0; --k) { int[] p = q.poll(); int i = p[0], j = p[1]; for (int l = 0; l < 4; ++l) { int x = i + dirs[l], y = j + 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.offer(new int[]{x, y}); maze[x][y] = '+'; } } } } return -1; }}class Solution {public: int nearestExit(vector<vector<char>> &maze, vector<int> &entrance) { int m = maze.size(), n = maze[0].size(); queue<vector<int>> q{{entrance}}; maze[entrance[0]][entrance[1]] = '+'; int ans = 0; vector<int> dirs = {-1, 0, 1, 0, -1}; while (!q.empty()) { ++ans; for (int k = q.size(); k > 0; --k) { auto p = q.front(); q.pop(); for (int l = 0; l < 4; ++l) { int x = p[0] + dirs[l], y = 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.push({x, y}); maze[x][y] = '+'; } } } } return -1; }};class Solution: def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int: m, n = len(maze), len(maze[0]) i, j = entrance q = deque([(i, j)]) maze[i][j] = '+' ans = 0 while q: ans += 1 for _ in range(len(q)): i, j = q . popleft() for a, b in [[0, - 1], [0, 1], [- 1, 0], [1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and maze[x][y] == '.': if x == 0 or x == m - 1 or y == 0 or y == n - 1: return ans q . append((x, y)) maze[x][y] = '+' return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.