Find Minimum Time to Reach Last Room II

Problem

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 one second for one move and two seconds for the next, alternating between the two.

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.

Examples

Example 1:


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

Output: 7

Explanation:

The minimum time required is 7 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 two seconds.

Example 2:


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

Output: 6

Explanation:

The minimum time required is 6 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 two seconds.
  * At time `t == 3`, move from room `(1, 1)` to room `(1, 2)` in one second.
  * At time `t == 4`, move from room `(1, 2)` to room `(1, 3)` in two seconds.

Example 3:


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

Output: 4

Constraints:

2 <= n == moveTime.length <= 750
2 <= m == moveTime[i].length <= 750
0 <= moveTime[i][j] <= 109

Solution

Method 1 - Dijkstra's shortest path

The problem requires finding the minimum time to reach the bottom-right corner of a grid, while adhering to certain rules:

Alternating movement cost: Moving between adjacent rooms alternates between 1 second and 2 seconds.
Room availability: Each room has a minimum time (moveTime[i][j]) before it can be entered.
- Delayed entry logic: If you arrive at a room before its moveTime, you must wait until the room becomes accessible.
Shortest path: Since adjacent rooms are connected, the problem resembles finding the shortest path in a weighted graph.

Approach

To solve this problem, we use a modified Dijkstra's algorithm because:

It handles weighted paths.
It ensures that we process rooms in increasing order of time to reach them.

Steps

Start from (0, 0) at time = 0:
- Begin at the top-left room and initialise its arrival time to 0.
Tracking the alternating movement cost:
- Movement between rooms alternates between taking 1 second and 2 seconds.
- Keep track of the current movement cost (step_cost) as you explore rooms.
Using a priority queue:
- Priority queue stores rooms to explore, prioritising those that can be reached sooner (lowest arrival time).
- Each room's priority queue entry includes:
  - Current time (t of arrival).
  - Current position (x, y).
  - Current movement cost (step_cost).
Wait logic for room availability:
- When attempting to enter a room (i, j):
  - Compute the wait time: max(0, moveTime[i][j] - current_time).
  - Account for this wait in the total time spent.
Optimality check:
- Maintain a matrix (arrivalTime) to store the earliest known time to reach each room. If you find a better (earlier) time for a room, update it and process it.
Update movement cost:
- After moving to a room, alternate the step cost (1 second ↔ 2 seconds) before exploring further.
Termination:
- Stop and return the time as soon as you reach the bottom-right room ((n-1, m-1)).

Code

Java

class Solution {
    public int minTimeToReach(int[][] moveTime) {
        // Store the input moveTime in a variable named roomMoveTime
        int[][] roomMoveTime = moveTime;  
        int totalRows = roomMoveTime.length;
        int totalCols = roomMoveTime[0].length;

        // Priority queue to store (current_time, row, col, step_cost)
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        priorityQueue.offer(new int[]{0, 0, 0, 1});  // Start at (0, 0) with time 0 and step cost 1
        
        int[][] minimumArrivalTime = new int[totalRows][totalCols];
        for (int[] row : minimumArrivalTime) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        minimumArrivalTime[0][0] = 0;

        // Directions for adjacent rooms (down, up, right, left)
        int[][] adjacentDirections = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!priorityQueue.isEmpty()) {
            int[] currentState = priorityQueue.poll();
            int currentTime = currentState[0], currentRow = currentState[1], currentCol = currentState[2], currentStepCost = currentState[3];

            // If we reached the target room (totalRows - 1, totalCols - 1)
            if (currentRow == totalRows - 1 && currentCol == totalCols - 1) {
                return currentTime;
            }

            // Explore adjacent rooms
            for (int[] direction : adjacentDirections) {
                int nextRow = currentRow + direction[0];
                int nextCol = currentCol + direction[1];

                if (nextRow >= 0 && nextRow < totalRows && nextCol >= 0 && nextCol < totalCols) {
                    int waitTime = Math.max(roomMoveTime[nextRow][nextCol] - currentTime, 0);
                    int newArrivalTime = currentTime + currentStepCost + waitTime;

                    // Only push to the queue if we found a better arrival time
                    if (newArrivalTime < minimumArrivalTime[nextRow][nextCol]) {
                        minimumArrivalTime[nextRow][nextCol] = newArrivalTime;
                        int nextStepCost = (currentStepCost == 2) ? 1 : 2;  // Alternate step cost
                        priorityQueue.offer(new int[]{newArrivalTime, nextRow, nextCol, nextStepCost});
                    }
                }
            }
        }

        return -1; // Return -1 if the target room is unreachable
    }
}

Python

class Solution:
    def minTimeToDungeon(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        
        # Priority queue stores (current_time, row, col, step_cost)
        pq = []
        heappush(pq, (0, 0, 0, 1))  # (time, x, y, step_cost)
        
        # Tracking the minimum arrival time at each room
        arrivalTime = [[float('inf')] * m for _ in range(n)]
        arrivalTime[0][0] = 0
        
        # Directions for adjacent rooms
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while pq:
            cur_time, x, y, cur_cost = heappop(pq)
            
            # If we reached the bottom-right corner, return the time
            if x == n - 1 and y == m - 1:
                return cur_time
            
            # Explore adjacent rooms
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < n and 0 <= ny < m:
                    wait_time = max(0, moveTime[nx][ny] - cur_time)
                    new_time = cur_time + cur_cost + wait_time
                    
                    # Only proceed if we found a better arrival time
                    if arrivalTime[nx][ny] > new_time:
                        arrivalTime[nx][ny] = new_time
                        next_cost = 2 if cur_cost == 1 else 1  # Alternate step cost
                        heappush(pq, (new_time, nx, ny, next_cost))
                        
        return -1  # Return -1 if unreachable

Complexity

⏰ Time complexity: O(n * m * log(n * m)). The priority queue requires log(n * m) operation for each of the n * m possible cells.
🧺 Space complexity: O(n + m). Accounts for the minimumArrivalTime matrix and priority queue.