#3341 - Find Minimum Time to Reach Last Room I

Medium • View on LeetCode • View on GitHub

Array Matrix Heap Priority Queue Graph Shortest Path

Problem Description

There is a dungeon with n x m rooms arranged as a grid.

You are given a 2D array moveTime of size n x m, where moveTime[i][j] represents the minimum time in seconds when you can start moving to that room. You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes exactly one second.

Return the minimum time to reach the room (n - 1, m - 1).

Two rooms are adjacent if they share a common wall, either horizontally or vertically.

Solution

/**
 * @param {number[][]} moveTime
 * @return {number}
 */
var minTimeToReach = function(moveTime) {
  const rows = moveTime.length;
  const cols = moveTime[0].length;
  const distances = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
  const pq = new PriorityQueue((a, b) => a[0] - b[0]);
  pq.enqueue([0, 0, 0]);
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

  distances[0][0] = 0;

  while (!pq.isEmpty()) {
    const [time, row, col] = pq.dequeue();

    if (row === rows - 1 && col === cols - 1) return time;

    if (time > distances[row][col]) continue;

    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;

      if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) continue;

      const newTime = Math.max(time, moveTime[newRow][newCol]) + 1;

      if (newTime < distances[newRow][newCol]) {
        distances[newRow][newCol] = newTime;
        pq.enqueue([newTime, newRow, newCol]);
      }
    }
  }

  return distances[rows - 1][cols - 1];
};