How do you solve Nearest Exit from Entrance in Maze on LeetCode?

Nearest Exit from Entrance in Maze (LeetCode #1926) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: BFS is optimal for shortest path problems in unweighted grids.

What is the brute force solution for Nearest Exit from Entrance in Maze?

The brute force approach for Nearest Exit from Entrance in Maze is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves exploring all possible paths from the entrance to find the nearest exit. This can be done using a recursive depth-first search (DFS) to check each direction until we reach an exit or exhaust all options. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Nearest Exit from Entrance in Maze?

Nearest Exit from Entrance in Maze uses the following concepts: Array, Breadth-First Search, Matrix. The recommended patterns to study are: Breadth-First Search, Graph Traversal.

What are the interview tips for Nearest Exit from Entrance in Maze?

Always clarify the problem constraints and edge cases. Discuss your thought process and approach before jumping into coding. Test your code with sample inputs to ensure correctness.

What are common mistakes when solving Nearest Exit from Entrance in Maze?

Not marking cells as visited, leading to infinite loops. Confusing the exit conditions, especially regarding the entrance.

#1926

Nearest Exit from Entrance in Maze

Medium

ArrayBreadth-First SearchMatrixBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses Breadth-First Search (BFS) to explore the maze level by level, ensuring that we find the shortest path to the nearest exit efficiently. BFS is ideal for unweighted grids like this because it explores all neighbors at the present depth before moving on to nodes at the next depth level.

⚙️

Algorithm

3 steps

1Step 1: Initialize a queue with the entrance position and a step count of 0.
2Step 2: While the queue is not empty, dequeue the front element and check if it's an exit.
3Step 3: If it's an exit, return the step count. Otherwise, enqueue all valid neighboring cells that haven't been visited yet, marking them as visited.

solution.py18 lines

1# Full working Python code
2from collections import deque
3from typing import List
4
5def nearest_exit(maze: List[List[str]], entrance: List[int]) -> int:
6    rows, cols = len(maze), len(maze[0])
7    queue = deque([(entrance[0], entrance[1], 0)])  # (x, y, steps)
8    maze[entrance[0]][entrance[1]] = '+'  # mark as visited
9    while queue:
10        x, y, steps = queue.popleft()
11        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
12            nx, ny = x + dx, y + dy
13            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '.':
14                if nx == 0 or nx == rows - 1 or ny == 0 or ny == cols - 1:
15                    return steps + 1
16                maze[nx][ny] = '+'  # mark as visited
17                queue.append((nx, ny, steps + 1))
18    return -1

ℹ

Complexity note: The time complexity is O(n) because each cell is processed at most once. The space complexity is O(n) due to the queue used for BFS, which can store all cells in the worst case.

1BFS is optimal for shortest path problems in unweighted grids.
2Marking cells as visited prevents cycles and redundant checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.