Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Moves alternate between one and two seconds, while rooms may require waiting before a move can start. The grid is bipartite: every step changes the parity of row + column. Thus every path to the same room has the same step-count parity, and the next move duration is determined by that room, not by which path reached it.

Approach

Use a min-heap of (arrivalTime, row, column, nextDuration) states, starting at time zero with a one-second next move. Keep one best-arrival value per room.

For each popped state and valid neighbor, compute max(arrivalTime, neighborThreshold) + nextDuration. If it improves the neighbor's distance, record it and enqueue a state with the duration switched between one and two. After processing the heap, return the destination's distance.

Earlier arrival dominates later arrival because waiting is allowed, and all arrivals at a room share the same next duration. This justifies the two-dimensional distance table even though the heap explicitly carries the alternating duration.

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n = len(moveTime)
        m = len(moveTime[0])
        q = [[0, 0, 0, 1]] # w, i, j, seconds
        dist = [[float('inf')] * m for _ in range(n)]
        dist[0][0] = 0

        while q:
            w, i, j, seconds = heapq.heappop(q)
            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni = di + i
                nj = dj + j
                if ni < 0 or nj < 0 or ni >= n or nj >= m:
                    continue
                curr = max(w, moveTime[ni][nj]) + seconds
                if curr < dist[ni][nj]:
                    dist[ni][nj] = curr
                    next_seconds = 2 if seconds == 1 else 1
                    heapq.heappush(q, [curr, ni, nj, next_seconds])

        return dist[n - 1][m - 1]

Complexity analysis

Let V = r * c grid cells and E = O(V) neighbor edges. Time: O((V + E) log V) = O(r * c log(r * c)). Auxiliary space: O(V).