#1926 - Nearest Exit from Entrance in Maze

MediumGraphs - BFS

Given an m × n matrix maze with empty cells '.' and walls '+', and an entrance position [row, col], return the number of steps in the shortest path from the entrance to the nearest exit. An exit is any empty cell on the border of the maze (not the entrance itself). Return -1 if no path exists.

Input	Output
maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]	1
maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]	2
maze = [[".","+"]	-1

Solution Space

Try it

/**
 * Returns the shortest path length from entrance to any border exit.
 *
 * @param maze     Grid of '.' (empty) and '+' (wall)
 * @param entrance Starting position [row, col]
 * @returns        Minimum steps to an exit, or -1 if unreachable
 */
export function nearestExit(maze: string[][], entrance: number[]): number {
  const m = maze.length;
  const n = maze[0].length;
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const queue: [number, number, number][] = [[entrance[0], entrance[1], 0]];
  maze[entrance[0]][entrance[1]] = "+"; // mark visited

  while (queue.length > 0) {
    const [row, col, steps] = queue.shift()!;

    for (const [dr, dc] of dirs) {
      const nr = row + dr;
      const nc = col + dc;

      if (nr < 0 || nr >= m || nc < 0 || nc >= n || maze[nr][nc] === "+")
        continue;

      // Is it a border cell? → exit found
      if (nr === 0 || nr === m - 1 || nc === 0 || nc === n - 1) {
        return steps + 1;
      }

      maze[nr][nc] = "+"; // mark visited
      queue.push([nr, nc, steps + 1]);
    }
  }

  return -1;
}

Approach: BFS from entrance – standard shortest-path BFS on a grid; the first border cell reached (other than the entrance) is the nearest exit.

Time: O(m · n) – each cell visited at most once.

Space: O(m · n) – queue can hold all cells in the worst case.

#994 Rotting Oranges

#215 Kth Largest Element in an Array