🤖 leetcode 2577. Minimum Time to Visit a Cell In a Grid | hard | graph

🗒️ Problems

2577. Minimum Time to Visit a Cell In a Grid - Leetcode

You are given a m x n matrix grid consisting of non-negative integers
where grid[row][col] represents the minimum time required to be able to visit the cell (row, col),
which means you can visit the cell (row, col)
only when the time you visit it is greater than or equal to grid[row][col].

You are standing in the top-left cell of the matrix in the 0th second,
and you must move to any adjacent cell in the four directions: up, down, left, and right.
Each move you make takes 1 second.

Return the minimum time required in which you can visit the bottom-right cell of the matrix.
If you cannot visit the bottom-right cell, then return -1.

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7
Explanation: One of the paths that we can take is the following:
- at t = 0, we are on the cell (0,0).
- at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
- at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
- at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
- at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
- at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
- at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
- at t = 7, we move to the cell (2,3). It is possible because grid[1][3] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.

🥳 Think differently

• When current time is NOT enough for visiting the next cell.
• It should spend some time by going to the previous cell back and forth.
• The rule should be found.

🤦‍♂️ First attempt

• After several trials, I ended up with the following code.
• But it fails.
• It seems that the problem is the location to check whether the node was visited or not.

var minimumTime = function (grid) {
  const [ROWS, COLS] = [grid.length, grid[0].length];

  if (grid[0][1] > 1 && grid[1][0] > 1) return -1;

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const isValid = (r, c) => !(r < 0 || r >= ROWS || c < 0 || c >= COLS);

  const seen = new Set();
  const genKey = (r, c) => `${r}:${c}`;

  // [ cost, r, c ]
  const minHeap = new MinPriorityQueue({ compare: (a, b) => a[0] - b[0] });
  minHeap.enqueue([0, 0, 0]);

  while (minHeap.size()) {
    let [time, r, c] = minHeap.dequeue();

    if (r === ROWS - 1 && c === COLS - 1) return time;

    seen.add(genKey(r, c));
    time += 1;

    for (const [dR, dC] of directions) {
      const newR = r + dR;
      const newC = c + dC;

      if (!isValid(newR, newC)) continue;
      // Checking visited before visiting is not good. It causes the error.
      if (seen.has(genKey(newR, newC))) continue;

      if (grid[newR][newC] <= time) {
        minHeap.enqueue([time, newR, newC]);
      } else {
        const isOdd = (grid[newR][newC] - time) % 2 === 1;
        const timeReq = grid[newR][newC] + isOdd;
        minHeap.enqueue([timeReq, newR, newC]);
      }
    }
  }
  return -1;
};

🥳 Comparison where to check the visited : [object Object]

💡 1. During next node validation

Basic BFS

const bfs = (graph) => {
  const queue = [START_NODE];
  const seen = new Set([START_NODE]);
  let res = 0;

  while (queue.length) {
    const len = queue.length;

    for (let i = 0; i < len; i++) {
      const [cur] = queue.shift();

      // if destination found, return
      if (cur === destination) return res;

      // do some logic

      for (const next of graph[cur]) {
        if (seen.has(next)) continue;

        seen.add(next);
        queue.push(next);
      }
    }
  }

  return res;
};

💡 2. Just before visiting a node, usually using heap

const bfs = (graph) => {
  const minHeap = new MinPriorityQueue({ compare: (a, b) => a[0] - b[0] });
  const seen = new Set([START_NODE]);
  let res = 0;

  while (minHeap.size()) {
    const [cost, r, c] = minHeap.dequeue();

    // do some logic
    // if destination found, return
    if (r === ROWS - 1 && c === COLS - 1) return cost;

    if (seen.has(genKey(r, c))) continue;
    seen.add(genKey(r, c));

    for (const [dR, dC] of directions) {
      const newR = r + dR;
      const newC = c + dC;

      if (!isValid(newR, newC)) continue;

      // some logic
      minHeap.enqueue([nextCost, newR, newC]);
    }
  }

  return res;
};

🔥 My Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumTime = function (grid) {
  const [ROWS, COLS] = [grid.length, grid[0].length];

  if (grid[0][1] > 1 && grid[1][0] > 1) return -1;

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const isValid = (r, c) => !(r < 0 || r >= ROWS || c < 0 || c >= COLS);

  const seen = new Set();
  const genKey = (r, c) => `${r}:${c}`;

  // [ cost, r, c ]
  const minHeap = new MinPriorityQueue({ compare: (a, b) => a[0] - b[0] });
  minHeap.enqueue([0, 0, 0]);

  while (minHeap.size()) {
    let [time, r, c] = minHeap.dequeue();

    if (r === ROWS - 1 && c === COLS - 1) return time;

    // Just actually visiting the node, check whether the node was already vistied or not.
    if (seen.has(genKey(r, c))) continue;
    seen.add(genKey(r, c));
    time += 1;

    for (const [dR, dC] of directions) {
      const newR = r + dR;
      const newC = c + dC;

      if (!isValid(newR, newC)) continue;

      if (grid[newR][newC] <= time) {
        minHeap.enqueue([time, newR, newC]);
      } else {
        const isOdd = (grid[newR][newC] - time) % 2 === 1;
        const timeReq = grid[newR][newC] + isOdd;
        minHeap.enqueue([timeReq, newR, newC]);
      }
    }
  }
  return -1;
};

🙆‍♂️ Time complexity: [object Object]