Find Minimum Time to Reach Last Room I
MedPrompt
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 <= 502 <= m == moveTime[i].length <= 500 <= moveTime[i][j] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
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
dfsfunction, iterate through all four adjacent neighbors(nr, nc). - For each valid neighbor, calculate the arrival time:
newTime = max(currentTime, moveTime[nr][nc]) + 1. - If
newTimeis less than the currentminTimes[nr][nc], updateminTimes[nr][nc]withnewTimeand 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.
Walkthrough
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.
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); } } } }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Let
nbe the number of rows andmbe 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 smallesttime. - 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
tis greater thanminTime[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), returntas 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
newTimeis less thanminTime[nr][nc], we have found a better path. UpdateminTime[nr][nc] = newTimeand enqueue the new state{newTime, nr, nc}.
- Calculate the time to start moving:
- Dequeue the element with the minimum time, let it be
Walkthrough
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.
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 }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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}); } } } } }}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))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}); } } } } }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.