Find Minimum Time to Reach Last Room I
Understanding the Problem
This problem models a grid where each cell has a "gate" that opens at a specific time. You start at (0, 0) at time 0 and want to reach (n-1, m-1) as fast as possible. To move into an adjacent cell, the current time must be at least that cell's moveTime value, so you may have to wait at your current cell until the neighbor's gate opens. The move itself always costs exactly 1 second.
That gives the arrival time at a neighbor (nr, nc) from cell (r, c):
The max accounts for waiting (if you arrive before the gate opens, you sit until moveTime[nr][nc]), and the + 1 is the travel cost.
This is a shortest path problem on a weighted grid graph. Each cell is a node, edges connect adjacent cells, and the edge weight depends on both your arrival time and the neighbor's gate time. Because the arrival time at a neighbor is always at least currentTime + 1, every edge weight is positive, which is the condition Dijkstra's algorithm requires.
Key Constraints:
2 <= n, m <= 50→ The grid has at most 2,500 cells, small enough for Dijkstra with a priority queue (O(nm log(nm))).0 <= moveTime[i][j] <= 10^9→ Gate times can force long waits, so cost is not uniform across moves. Plain BFS, which assumes every edge costs the same, does not apply. The arrival time is bounded by roughly10^9 + 2500, which fits in a signed 32-bit integer, sointis safe in every language here.
Approach 1: BFS with Relaxation (Naive)
Intuition
The grid structure suggests BFS, but standard BFS only finds shortest paths when every edge costs the same. Here the cost to move into a room depends on that room's gate time, so two paths to the same room can produce very different arrival times: one path might pass through rooms with high gate times that force waiting.
This approach keeps a queue of cells along with the arrival time recorded for each, and relaxes edges the way Bellman-Ford does. Pop a cell, compute the arrival time at each neighbor, and if that beats the neighbor's best-known time, record it and enqueue the neighbor. Repeat until the queue drains, which happens once no cell's time can improve further.
Processing in FIFO order means a cell can be dequeued with a time that later gets improved. Its neighbors then get relaxed again from the better time, so the same cell may be enqueued and reprocessed several times. The answer is still correct, but the repeated work is what the next approach removes.
Algorithm
- Create a 2D
distarray initialized to infinity. Setdist[0][0] = 0. - Add
(0, 0)to a queue with time 0. - While the queue is not empty, dequeue
(r, c)with its time. - If the dequeued time is worse than the stored dist, skip this entry.
- For each adjacent cell
(nr, nc), computearrivalTime = max(time, moveTime[nr][nc]) + 1. - If
arrivalTime < dist[nr][nc], updatedist[nr][nc]and enqueue(nr, nc, arrivalTime). - Return
dist[n-1][m-1].
Visualization and Code
Loading animation...
- Time Complexity: O(V^2) in the worst case, where V = n * m. Each cell can be enqueued multiple times as shorter paths are discovered.
- Space Complexity: O(V). The dist array takes O(n m) space, and the queue can hold at most O(n m) entries.
The reprocessing comes from the FIFO order. Dijkstra's algorithm removes it by always extracting the cell with the smallest arrival time next, so each cell is finalized exactly once.
Approach 2: Dijkstra's Algorithm (Optimal)
Intuition
Each edge weight here is positive: the arrival time at a neighbor, max(t, moveTime[nr][nc]) + 1, is always at least t + 1. That is the condition Dijkstra's algorithm needs, so it computes the minimum arrival time to every cell.
Dijkstra extracts the unvisited cell with the smallest known arrival time, finalizes it, and relaxes its neighbors. A min-heap keyed on arrival time provides the next cell to process in logarithmic time. For each cell (r, c) popped with time t, the arrival time at neighbor (nr, nc) is max(t, moveTime[nr][nc]) + 1; if that beats the recorded distance to (nr, nc), update it and push the new entry.
When a cell is popped from the heap, its recorded time is final. Every entry still in the heap has a time greater than or equal to the popped one, and every edge adds at least 1 second, so no path discovered later can reach that cell sooner. Each cell is therefore finalized once, which is why the early exit at the destination is safe: the first time (n-1, m-1) comes off the heap, its time cannot be improved.
Algorithm
- Create a 2D
distarray initialized to infinity. Setdist[0][0] = 0. - Push
(0, 0, 0)(time, row, col) into a min-heap. - While the heap is not empty:
- Pop the cell
(time, r, c)with the smallest time. - If
(r, c)is(n-1, m-1), returntime. - If
time > dist[r][c], skip (we already found a shorter path). - For each adjacent cell
(nr, nc): - Compute
arrivalTime = max(time, moveTime[nr][nc]) + 1. - If
arrivalTime < dist[nr][nc], updatedist[nr][nc]and push to the heap. - Return
dist[n-1][m-1].
Visualization and Code
Loading animation...
- Time Complexity: O(V log V), where V = n * m. Each cell is added to the heap at most once per neighbor (4 neighbors), giving O(4V) = O(V) heap insertions. Each insertion and extraction is O(log V).
- Space Complexity: O(V). The dist array uses O(n m) space. The heap holds at most O(n m) entries.