# Find Minimum Time to Reach Last Room I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-time-to-reach-last-room-i
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Matrix, Graph
---
## 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 **after** which the room opens and can be moved to. 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] <= 109`

# Approaches
## Brute-Force Depth First Search (TLE)
This approach attempts to solve the problem by exploring all possible paths from the start `(0, 0)` to the end `(n-1, m-1)` using a Depth First Search (DFS). It recursively explores each path, calculates the total time taken, and keeps track of the minimum time found to reach the destination. To avoid getting stuck in infinite loops, this method requires pruning branches of the search that are already known to be non-optimal. However, due to the massive number of possible paths in a grid, this method is too slow for the problem's constraints.
**Time:** O(4^(n*m)). In the worst case, the algorithm explores an exponential number of paths, leading to a very high time complexity. · **Space:** O(n * m) for the recursion stack in the worst case and the `minTimes` array.
**Pros:** Conceptually simple to understand for those familiar with recursion.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.; It re-explores rooms multiple times without an efficient strategy, leading to an exponential number of computations.; Deep recursion might lead to a 'StackOverflowError' on large grids.
### Explanation
The core idea is to use a recursive function that represents the state `(row, col, currentTime)`. We maintain a global 2D array, `minTimes`, to store the minimum arrival time discovered so far for each room. This array helps in pruning the search space. When exploring from a room `(r, c)` at `currentTime`, we look at its neighbors. For a neighbor `(nr, nc)`, the earliest we can start moving is `max(currentTime, moveTime[nr][nc])`. Since moving takes one second, the arrival time at the neighbor will be `max(currentTime, moveTime[nr][nc]) + 1`. If this new time is better than the recorded `minTimes[nr][nc]`, we update it and continue the search from the neighbor. This is essentially a brute-force exploration of the state space, which is highly inefficient as it doesn't prioritize exploring more promising paths first.

```java
import java.util.Arrays;

class Solution {
    private int[][] moveTime;
    private int n, m;
    private long[][] minTimes;
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int findMinimumTime(int[][] moveTime) {
        this.moveTime = moveTime;
        this.n = moveTime.length;
        this.m = moveTime[0].length;
        this.minTimes = new long[n][m];

        for (int i = 0; i < n; i++) {
            Arrays.fill(minTimes[i], Long.MAX_VALUE);
        }

        minTimes[0][0] = 0;
        dfs(0, 0, 0);
        
        return (int) minTimes[n - 1][m - 1];
    }

    private void dfs(int r, int c, long currentTime) {
        // Pruning: if current path is already longer than the best path to destination, stop.
        if (currentTime >= minTimes[n - 1][m - 1]) {
            return;
        }

        for (int[] dir : dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                long startTime = Math.max(currentTime, moveTime[nr][nc]);
                long newTime = startTime + 1;

                if (newTime < minTimes[nr][nc]) {
                    minTimes[nr][nc] = newTime;
                    dfs(nr, nc, newTime);
                }
            }
        }
    }
}
```
### Algorithm
- Initialize a 2D array `minTimes[n][m]` with a very large value to store the minimum time to reach each room.
- Set `minTimes[0][0] = 0`.
- Define a recursive function, for example, `dfs(r, c, currentTime)`.
- In the `dfs` function, iterate through all four adjacent neighbors `(nr, nc)`.
- For each valid neighbor, calculate the arrival time: `newTime = max(currentTime, moveTime[nr][nc]) + 1`.
- If `newTime` is less than the current `minTimes[nr][nc]`, update `minTimes[nr][nc]` with `newTime` and make a recursive call: `dfs(nr, nc, newTime)`.
- The initial call is `dfs(0, 0, 0)`.
- The final answer is the value stored in `minTimes[n-1][m-1]` after the search completes.

## Dijkstra's Algorithm on Grid
This problem can be modeled as finding the shortest path in a weighted graph. The rooms of the grid act as vertices, and an edge exists between any two adjacent rooms. The cost (or weight) of traversing an edge is dynamic and depends on the arrival time at the current room and the `moveTime` of the destination room. Dijkstra's algorithm is the ideal solution for such single-source shortest path problems on graphs with non-negative edge weights. By using a priority queue, it efficiently explores the grid, always expanding the path with the current minimum arrival time, guaranteeing that the first time we reach the destination, it is through the fastest route.
**Time:** O(n * m * log(n * m)). The graph has `V = n * m` vertices. Each vertex is enqueued and dequeued at most once. The priority queue operations take `O(log V)` time, leading to the overall complexity. · **Space:** O(n * m). The space is used for the `minTime` 2D array and the priority queue, which can store up to O(n * m) elements in the worst case.
**Pros:** Guaranteed to find the optimal solution (the minimum time).; Highly efficient and the standard algorithm for this type of problem.; Passes within the given time and memory constraints.
**Cons:** Slightly more complex to implement compared to a basic DFS.; Requires additional space for the priority queue.
### Explanation
We use a priority queue to implement Dijkstra's algorithm. The priority queue will store states as `[time, row, col]` and will be ordered by `time` in ascending order. We also use a 2D array, `minTime`, to keep track of the minimum time found so far to reach each cell, initialized to infinity.

The algorithm starts by pushing the initial state `[0, 0, 0]` into the priority queue and setting `minTime[0][0] = 0`. Then, it repeatedly extracts the state with the minimum time from the queue. For the extracted state `(t, r, c)`, it explores all valid neighbors. For each neighbor `(nr, nc)`, it calculates the potential arrival time `newTime = max(t, moveTime[nr][nc]) + 1`. If this `newTime` is an improvement over the recorded `minTime[nr][nc]`, it updates `minTime[nr][nc]` and pushes the new state `[newTime, nr, nc]` into the queue. This process continues until the destination `(n-1, m-1)` is reached.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int findMinimumTime(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;

        long[][] minTime = new long[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(minTime[i], Long.MAX_VALUE);
        }

        // Priority Queue stores {time, row, col}
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

        // Start at (0, 0) at time 0
        minTime[0][0] = 0;
        pq.offer(new long[]{0, 0, 0});

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long t = current[0];
            int r = (int) current[1];
            int c = (int) current[2];

            // If we found a shorter path already, skip
            if (t > minTime[r][c]) {
                continue;
            }

            // If we reached the destination, return the time
            if (r == n - 1 && c == m - 1) {
                return (int) t;
            }

            // Explore neighbors
            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    // Time to start moving from (r, c)
                    long startTime = Math.max(t, moveTime[nr][nc]);
                    // Time of arrival at (nr, nc)
                    long newTime = startTime + 1;

                    if (newTime < minTime[nr][nc]) {
                        minTime[nr][nc] = newTime;
                        pq.offer(new long[]{newTime, nr, nc});
                    }
                }
            }
        }
        
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
- Let `n` be the number of rows and `m` be the number of columns.
- Create a 2D array `minTime[n][m]` and initialize all its values to infinity. This array will store the minimum time to reach each room.
- Set `minTime[0][0] = 0`.
- Create a min-priority queue to store tuples of `{time, row, col}`. The priority queue will always return the tuple with the smallest `time`.
- Add the starting state `{0, 0, 0}` to the priority queue.
- While the priority queue is not empty:
  - Dequeue the element with the minimum time, let it be `(t, r, c)`.
  - If `t` is greater than `minTime[r][c]`, it means we have found a shorter path to this room before, so we skip this element.
  - If `(r, c)` is the destination `(n-1, m-1)`, return `t` as it's the minimum possible time.
  - For each adjacent neighbor `(nr, nc)` of `(r, c)`:
    - Calculate the time to start moving: `startTime = max(t, moveTime[nr][nc])`.
    - Calculate the arrival time at the neighbor: `newTime = startTime + 1`.
    - If `newTime` is less than `minTime[nr][nc]`, we have found a better path. Update `minTime[nr][nc] = newTime` and enqueue the new state `{newTime, nr, nc}`.

# Solutions
### Java

```java
class Solution {
public
  int minTimeToReach(int[][] moveTime) {
    int n = moveTime.length;
    int m = moveTime[0].length;
    int[][] dist = new int[n][m];
    for (var row : dist) {
      Arrays.fill(row, Integer.MAX_VALUE);
    }
    dist[0][0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);
    pq.offer(new int[]{0, 0, 0});
    int[] dirs = {-1, 0, 1, 0, -1};
    while (true) {
      int[] p = pq.poll();
      int d = p[0], i = p[1], j = p[2];
      if (i == n - 1 && j == m - 1) {
        return d;
      }
      if (d > dist[i][j]) {
        continue;
      }
      for (int k = 0; k < 4; k++) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < m) {
          int t = Math.max(moveTime[x][y], dist[i][j]) + 1;
          if (dist[x][y] > t) {
            dist[x][y] = t;
            pq.offer(new int[]{t, x, y});
          }
        }
      }
    }
  }
}

```

### Python

```python
class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int: n, m = len(moveTime), len(moveTime[0]) dist = [[inf] * m for _ in range(n)] dist[0][0] = 0 pq = [(0, 0, 0)] dirs = (- 1, 0, 1, 0, - 1) while 1: d, i, j = heappop(pq) if i == n - 1 and j == m - 1: return d if d > dist[i][j]: continue for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < n and 0 <= y < m: t = max(moveTime[x][y], dist[i][j]) + 1 if dist[x][y] > t: dist[x][y] = t heappush(pq, (t, x, y))

```

### CPP

```cpp
class Solution {
public:
  int minTimeToReach(vector<vector<int>> &moveTime) {
    int n = moveTime.size();
    int m = moveTime[0].size();
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    dist[0][0] = 0;
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    pq.push({0, 0, 0});
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (1) {
      auto [d, i, j] = pq.top();
      pq.pop();
      if (i == n - 1 && j == m - 1) {
        return d;
      }
      if (d > dist[i][j]) {
        continue;
      }
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < m) {
          int t = max(moveTime[x][y], dist[i][j]) + 1;
          if (dist[x][y] > t) {
            dist[x][y] = t;
            pq.push({t, x, y});
          }
        }
      }
    }
  }
};

```