#3342

Medium

LeetCode Problem Workspace

Find Minimum Time to Reach Last Room II

Calculate the minimum time to reach the last room in a grid with alternating move times using array and graph patterns.

array graph heap priority queue matrix shortest path

Problem Statement

You are in a dungeon represented as an n x m grid of rooms. Each room move has alternating travel times: moving once costs 1 second, then the next move costs 2 seconds, and this pattern repeats. You are given moveTime[i][j], the earliest time you can start moving into room (i, j). Starting at room (0, 0) at time 0, determine how quickly you can reach the last room.

Return the minimum time required to reach room (n - 1, m - 1). You may only move to adjacent rooms (up, down, left, right). Use the alternating movement pattern and moveTime constraints to find the optimal path, combining array traversal and graph shortest path strategies to handle the state of odd or even moves.

Examples

Example 1

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

Output: 7

The minimum time required is 7 seconds.

Example 2

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

Output: 6

The minimum time required is 6 seconds.

Example 3

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

Output: 4

Example details omitted.

Constraints

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

Solution Approach

Model as Shortest Path with State

Treat each room as a node in a graph and include the parity of the last move (odd or even) as part of the state. This allows tracking whether the next move costs 1 or 2 seconds. Update each reachable neighbor using the maximum of current time plus move cost and moveTime constraint.

Use Priority Queue for Efficient Propagation

Implement a min-heap to always process the room with the earliest arrival time. Push neighbors with updated times and state into the heap. This ensures that the first time you reach the target room is the minimum possible time.

Handle MoveTime Constraints

For each neighbor, compute the next possible start time by comparing the calculated arrival time with moveTime[i][j]. If the current time is less than moveTime[i][j], wait until moveTime[i][j] before moving. This prevents illegal early moves and ensures correctness.

Complexity Analysis

Metric	Value
Time	O(nm \log(nm))
Space	O(nm)

Time complexity is O(nm log(nm)) because each room state is processed once in a priority queue. Space complexity is O(nm) to store earliest reachable times for each room and move parity.

What Interviewers Usually Probe

Expect you to notice alternating move costs and track state accordingly.
Hinting at using a priority queue suggests shortest path with state propagation.
Ask why naive BFS without parity fails for certain moveTime patterns.

Common Pitfalls or Variants

Common pitfalls

Ignoring the odd/even move cost alternation leads to incorrect minimum times.
Failing to wait until moveTime[i][j] for each move can produce invalid paths.
Not tracking separate states for each parity may overestimate or underestimate total time.

Follow-up variants

Allow diagonal moves in addition to cardinal directions, requiring updated state transitions.
Change move costs to a repeating pattern beyond 1 and 2 seconds, adjusting state tracking.
Introduce obstacles with infinite moveTime to test unreachable paths.

FAQ

What is the main pattern to use in Find Minimum Time to Reach Last Room II?

The problem is an array plus graph pattern where each node carries state for move parity to handle alternating move times.

Can I move diagonally in this problem?

No, you can only move to adjacent rooms up, down, left, or right; diagonals are not allowed in the base problem.

Why does a simple BFS fail?

Simple BFS ignores the alternating move costs and moveTime constraints, producing incorrect minimum arrival times.

What data structure is recommended for efficiency?

A min-heap or priority queue is recommended to always process the room with the earliest reachable time.

How large can the grid be?

Grids can be up to 750 x 750 rooms, so an efficient O(nm log(nm)) solution is necessary to avoid timeouts.

terminal

Solution

Solution 1: Dijkstra's Algorithm

We define a two-dimensional array $\textit{dist}$, where $\textit{dist}[i][j]$ represents the minimum time required to reach room $(i, j)$ from the starting point. Initially, we set all elements in the $\textit{dist}$ array to infinity, and then set the $\textit{dist}$ value of the starting point $(0, 0)$ to $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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]) + (i + j) % 2 + 1
                    if dist[x][y] > t:
                        dist[x][y] = t
                        heappush(pq, (t, x, y))

Continue Practicing

#3341 find minimum time to reach last room i #3286 find a safe walk through a grid #2577 minimum time to visit a cell in a grid