3627. Find Minimum Time To Reach Last Room I¶

Difficulty: Medium

3627. Find Minimum Time to Reach Last Room I

Medium

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.

Example 1:

Input: moveTime = [[0,4],[4,4]]

Output: 6

Explanation:

The minimum time required is 6 seconds.

At time t == 4, move from room (0, 0) to room (1, 0) in one second.
At time t == 5, move from room (1, 0) to room (1, 1) in one second.

Example 2:

Input: moveTime = [[0,0,0],[0,0,0]]

Output: 3

Explanation:

The minimum time required is 3 seconds.

At time t == 0, move from room (0, 0) to room (1, 0) in one second.
At time t == 1, move from room (1, 0) to room (1, 1) in one second.
At time t == 2, move from room (1, 1) to room (1, 2) in one second.

Example 3:

Input: moveTime = [[0,1],[1,2]]

Output: 3

Constraints:

2 <= n == moveTime.length <= 50
2 <= m == moveTime[i].length <= 50
0 <= moveTime[i][j] <= 10⁹

Solution¶

class Solution {
    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[2], b[2]));
        long[][] dist = new long[n][m];
        for (long curr[] : dist) Arrays.fill(curr, (long)(Long.MAX_VALUE) / 10);
        pq.offer(new long[]{0, 0, 0});
        dist[0][0] = 0;
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long x = current[0];
            long y = current[1];
            long time = current[2];
            if (x == n - 1 && y == m - 1) return (int)(time);
            for (int[] dire : dir) {
                int newX = (int)(x + dire[0]);
                int newY = (int)(y + dire[1]);
                if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                    long current1 = (long)(Math.max(time, moveTime[newX][newY])) + 1;
                    if (current1 < dist[newX][newY]) {
                        dist[newX][newY] = current1;
                        pq.offer(new long[]{newX, newY, current1});
                    }
                }
            }
        }
        return -1;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here