Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Reaching a room earlier cannot make future travel worse because you may wait. If the current time is time, moving to a neighbor can begin no earlier than both time and that neighbor's threshold. Its arrival time is therefore max(time, threshold) + 1.

Approach

Initialize every room's best arrival time to infinity except the starting room, which is reached at time zero. Put that starting state in a min-heap ordered by arrival time.

Repeatedly remove the earliest queued state and inspect its four in-bounds neighbors. Calculate the candidate arrival time with the waiting formula. Whenever it improves the neighbor's recorded time, update the distance and push the new state. Return the destination's recorded distance after processing the queue.

The transition is nondecreasing in the departure time, so waiting preserves the shortest-path principle behind Dijkstra's algorithm. Importantly, the room threshold limits when the move may start; the one-second travel time is added afterward.

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

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

        return dist[-1][-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).