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 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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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:

1
2
3
4


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^9

Solution

Method 1 - Using Dijkstra’s algorithm

We need to find the minimum time required to reach the destination room (n-1, m-1) starting from (0, 0). This is an optimisation problem where we evaluate paths while adhering to the condition that each room has its own restriction defined by moveTime[i][j]. A room can only be entered after its restriction time has elapsed.

The grid can be seen as a graph, and moving between rooms represents edges. Using a priority queue (min-heap) is ideal for this task because we attempt to explore rooms with the smallest valid entry time first.

Approach

  1. Initialisation:

    • Using Dijkstra’s-like algorithm, maintain a priority queue to store the current position (x, y) and the time required to enter that room.
    • Create a 2D array visited to ensure we don’t revisit rooms unnecessarily.

  2. Algorithm:

    • Push the starting room (0, 0) into the priority queue with time 0.
    • For each position in the queue, evaluate its adjacent rooms (top, bottom, left, right).
    • For every adjacent room, calculate the time to move to that room and ensure it meets the moveTime constraint.
    • Update the queue with the calculated valid time only if the room hasn’t been visited yet.

  3. Termination:

    • Stop the algorithm when (n-1, m-1) is reached, and return the minimum time recorded.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int minTimeToReachRoom(int[][] moveTime) {
        int n = moveTime.length, m = moveTime[0].length;
        boolean[][] visited = new boolean[n][m];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // Min-heap
        
        pq.offer(new int[]{0, 0, 0}); // Format: {time, x, y}
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int t = cur[0], x = cur[1], y = cur[2];
            
            if (visited[x][y]) {
                continue; // Skip already visited
            }
            visited[x][y] = true;
            
            if (x == n - 1 && y == m - 1) { // Destination reached
                return t;
            }
            
            int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (int[] dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny]) {
                    int nt = Math.max(t + 1, moveTime[nx][ny]); // Wait until accessible
                    pq.offer(new int[]{nt, nx, ny});
                }
            }
        }
        
        return -1; // If unreachable
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        INF = float("inf")
        n, m = len(moveTime), len(moveTime[0])
        
        d = [[INF] * m for _ in range(n)]  # Distance array
        v = [[False] * m for _ in range(n)]  # Visited array
        
        d[0][0] = 0
        pq = []  # Priority queue for (time, x, y)
        heappush(pq, (0, 0, 0))  # Start at (0, 0) with time 0
        
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # Movement directions
        
        while pq:
            t, x, y = heappop(pq)  # Extract state with min time
            if v[x][y]:
                continue
            v[x][y] = True
            
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                # Check bounds
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                dist = max(d[x][y], moveTime[nx][ny]) + 1  # Calculate time for neighbour
                if d[nx][ny] > dist:
                    d[nx][ny] = dist
                    heappush(pq, (dist, nx, ny))
        
        return d[n - 1][m - 1]  # Return distance to bottom-right corner

Complexity

  • ⏰ Time complexity: O(n * m log(n * m)). - The grid contains n * m cells, and processing each cell involves prioritised exploration using a heap which takes logarithmic time.
  • 🧺 Space complexity: O(n * m). - Space required for visited array and grid processing.