LeetCode 1926: Nearest Exit from Entrance in Maze Solution

Master LeetCode problem 1926 (Nearest Exit from Entrance in Maze), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1926. Nearest Exit from Entrance in Maze

Medium

Array Breadth-First Search Matrix

Problem Explanation

Explanation:

To solve this problem, we can use a breadth-first search (BFS) algorithm starting from the entrance cell. We will explore all possible paths in the maze while keeping track of the distance from the entrance. We will stop the search as soon as we find the nearest exit at the border of the maze.

Initialize a queue for BFS and mark the entrance cell as visited.
Start BFS by iterating over the neighbors of the current cell:
- If a neighbor is a valid empty cell and has not been visited, add it to the queue with an increased distance.
- If a neighbor is at the border of the maze, return the distance as the result.
If no exit is found, return -1.

Time Complexity: O(mn) where m and n are the dimensions of the maze. Space Complexity: O(mn) for the queue and visited array.

Solution Code

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(entrance);
        maze[entrance[0]][entrance[1]] = '+';
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                for (int[] dir : dirs) {
                    int newRow = curr[0] + dir[0];
                    int newCol = curr[1] + dir[1];
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && maze[newRow][newCol] == '.') {
                        if (newRow == 0 || newRow == m - 1 || newCol == 0 || newCol == n - 1) {
                            return steps + 1;
                        }
                        maze[newRow][newCol] = '+';
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1926 (Nearest Exit from Entrance in Maze)?

This page provides optimized solutions for LeetCode problem 1926 (Nearest Exit from Entrance in Maze) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1926 (Nearest Exit from Entrance in Maze)?

The time complexity for LeetCode 1926 (Nearest Exit from Entrance in Maze) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1926 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1926 in Java, C++, or Python.

Back to LeetCode Solutions