LeetCode: Nearest Exit from Entrance in Maze Solution

Approach

BFS will guarantee the nearest exit on the first valid

Mark a coordinate as visited before pusing to the queue. This is important, as it would avoid duplication, which will lead to TLE or MLE.

Implementation

1var nearestExit = function (maze, entrance) {
2  const dirs = [
3    [-1, 0],
4    [1, 0],
5    [0, 1],
6    [0, -1],
7  ]
8
9  const [numberOfRows, numberOfCols] = [maze.length, maze[0].length]
10  const [startRow, startCol] = entrance
11  const queue = new MyQueue()
12  maze[startRow][startCol] = "+"
13  queue.enqueue([startRow, startCol, 0])
14
15  let res = -1
16
17  bfs: while (queue.size > 0) {
18    const [currentRow, currentCol, currentDistance] = queue.dequeue()
19
20    for (const [deltaRow, deltaCol] of dirs) {
21      const [nextRow, nextCol, nextDistance] = [
22        currentRow + deltaRow,
23        currentCol + deltaCol,
24        currentDistance + 1,
25      ]
26
27      if (
28        0 <= nextRow &&
29        nextRow < numberOfRows &&
30        0 <= nextCol &&
31        nextCol < numberOfCols &&
32        maze[nextRow][nextCol] === "."
33      ) {
34        if (
35          [0, numberOfRows - 1].includes(nextRow) ||
36          [0, numberOfCols - 1].includes(nextCol)
37        ) {
38          res = nextDistance
39          break bfs
40        }
41
42        maze[nextRow][nextCol] = "+"
43        queue.enqueue([nextRow, nextCol, nextDistance])
44      }
45    }
46  }
47
48  return res
49}
50
51class Node {
52  constructor(val, next = null) {
53    this.val = val
54    this.next = next
55  }
56}
57
58class MyQueue {
59  constructor() {
60    this.head = null
61    this.tail = null
62    this.size = 0
63  }
64
65  enqueue(val) {
66    const node = new Node(val)
67
68    this.size++
69
70    if (!this.tail) {
71      this.head = this.tail = node
72      return
73    }
74
75    this.tail.next = node
76    this.tail = this.tail.next
77  }
78
79  dequeue() {
80    if (!this.head) return null
81
82    const node = this.head
83    this.size--
84    this.head = this.head.next
85
86    if (!this.head) this.tail = null
87
88    return node.val
89  }
90
91  peek() {
92    if (!this.head) return null
93
94    return this.head.val
95  }
96}

References

Original problem