Nearest Exit from Entrance in Maze - Practice Coding Problems

Nearest Exit from Entrance in Maze - 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.

Input & Output

Example 1 — Basic Maze

$ Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+",".","."]], entrance = [1,2]

› Output: 1

💡 Note: Start at (1,2). The nearest exit is at (1,3) which is 1 step to the right. This is a border cell.

Example 2 — No Exit Available

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

› Output: -1

💡 Note: Start at (1,0). Although this is a border cell, it's the entrance so doesn't count as exit. All other border cells are walls (+), so no exit exists.

Example 3 — Multiple Paths

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

› Output: 1

💡 Note: Start at (1,0). Can go up to (0,0) in 1 step, which is a border cell and serves as an exit.

Constraints

maze.length == m
maze[i].length == n
1 ≤ m, n ≤ 100
maze[i][j] is either '.' or '+'
entrance.length == 2
0 ≤ entrance_row < m
0 ≤ entrance_col < n
entrance will always be an empty cell

Visualization

Tap to expand

Understanding the Visualization

Input

Maze with walls (+), paths (.), and entrance position

Process

Use BFS to explore paths level by level until border reached

Output

Return minimum steps to reach any exit, or -1 if impossible

Key Takeaway

🎯 Key Insight: BFS guarantees shortest path by exploring all cells at distance k before distance k+1

Asked in

G Google 25 a Amazon 30 m Microsoft 20 f Facebook 15

The key insight is to use BFS for shortest path problems. BFS explores cells level by level, guaranteeing that the first exit found is at minimum distance. Best approach is BFS with queue. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Breadth-First Search (Optimal)	O(m×n)	O(m×n)	Use BFS to find shortest path by exploring cells level by level
Brute Force DFS	O(4^(m×n))	O(m×n)	Try all possible paths using DFS and track minimum steps to any exit

Breadth-First Search (Optimal) — Algorithm Steps

Start BFS from entrance using a queue
Explore all adjacent empty cells level by level
Mark visited cells to avoid revisiting
Return steps when first exit (border cell) is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 0

Start at entrance, add to queue

Level 1

Explore all adjacent cells, add unvisited to queue

Level 2

Continue until exit found - guaranteed shortest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct QueueNode {
    int row, col, steps;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

void enqueue(struct Queue* q, int row, int col, int steps) {
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->row = row;
    newNode->col = col;
    newNode->steps = steps;
    newNode->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

struct QueueNode* dequeue(struct Queue* q) {
    if (q->front == NULL) return NULL;
    
    struct QueueNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    
    return temp;
}

int isEmpty(struct Queue* q) {
    return q->front == NULL;
}

int solution(char maze[][1000], int m, int n, int* entrance) {
    int startRow = entrance[0], startCol = entrance[1];
    
    struct Queue q = {NULL, NULL};
    int visited[1000][1000];
    memset(visited, 0, sizeof(visited));
    
    enqueue(&q, startRow, startCol, 0);
    visited[startRow][startCol] = 1;
    
    int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    while (!isEmpty(&q)) {
        struct QueueNode* current = dequeue(&q);
        int row = current->row, col = current->col, steps = current->steps;
        
        if ((row == 0 || row == m-1 || col == 0 || col == n-1) && 
            (row != startRow || col != startCol)) {
            free(current);
            return steps;
        }
        
        for (int i = 0; i < 4; i++) {
            int newRow = row + directions[i][0];
            int newCol = col + directions[i][1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                maze[newRow][newCol] == '.' && !visited[newRow][newCol]) {
                visited[newRow][newCol] = 1;
                enqueue(&q, newRow, newCol, steps + 1);
            }
        }
        
        free(current);
    }
    
    return -1;
}

int main() {
    char maze[1000][1000];
    int entrance[2] = {1, 0};
    int m = 3, n = 3;
    
    // Example maze
    maze[0][0] = '+'; maze[0][1] = '+'; maze[0][2] = '.';
    maze[1][0] = '.'; maze[1][1] = '.'; maze[1][2] = '.';
    maze[2][0] = '+'; maze[2][1] = '.'; maze[2][2] = '.';
    
    printf("%d\n", solution(maze, m, n, entrance));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each cell is visited at most once during BFS traversal

✓ Linear Growth

Space Complexity

O(m×n)

Queue can hold up to m×n cells, plus visited array of size m×n

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~15 min Avg. Time

867 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler