LeetCode 3342 - Find Minimum Time to Reach Last Room II

LeetCode Problem 3342

Difficulty: 🟡 Medium
Topics: Array, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path

Solution

Problem Understanding

This problem describes a dungeon represented as an n x m grid of rooms, where each room has a constraint on the earliest time you can enter it, given by the 2D array moveTime. You start at the top-left corner (0, 0) at time t = 0 and want to reach the bottom-right corner (n-1, m-1) in the minimum possible time. Movement is restricted to adjacent rooms, either horizontally or vertically, and each move alternates between taking one second and two seconds.

The input moveTime[i][j] guarantees that you cannot enter room (i, j) before that time. The output should be a single integer representing the minimum time required to reach the last room, obeying the movement timing constraints.

Constraints indicate that n and m can each be up to 750, which makes naive brute-force approaches that explore all paths infeasible. moveTime[i][j] values can be large (up to 1e9), so any approach relying on iterating over time steps would also be too slow.

Edge cases include:

1. The first room moveTime[0][0] is always 0.
2. The timing alternates strictly between 1-second and 2-second moves, so care must be taken to maintain this pattern.
3. Rooms that are blocked until a later time may force you to wait at the previous room until the earliest allowable move time.

Understanding this problem fully requires modeling both the position and the parity of the move (whether the next move takes 1 or 2 seconds) as part of the state.

Approaches

The brute-force approach would be a depth-first search (DFS) that explores every possible path from (0, 0) to (n-1, m-1). At each room, it would recursively explore all adjacent moves, compute the earliest time for each, and return the minimum. While this is correct, it is extremely inefficient for the maximum grid size (750 x 750), as the number of possible paths grows exponentially.

The optimal approach is to model this as a shortest-path problem on a graph, where each cell is a node, edges connect adjacent rooms, and edge weights alternate between 1 and 2 seconds. We also need to respect the moveTime constraints, meaning you may need to wait before moving. Dijkstra's algorithm, adapted to track the alternating step duration and potential wait time, is ideal because it always expands the node with the current minimum time.

Key insight: for each move, compute the next available time based on the current time and the room's moveTime, adjusting for the 1-second / 2-second alternating pattern. Using a priority queue ensures that we always expand the room that can be reached the earliest, guaranteeing correctness.

Algorithm Walkthrough

1. Initialize a priority queue and push the starting room (0, 0) with time = 0.

2. Create a 2D array minTime to track the minimum time at which each room can be reached. Initialize all values to infinity except minTime[0][0] = 0.

3. Define possible moves: up, down, left, right.

4. While the priority queue is not empty:

5. Pop the room with the smallest current time.

6. If this room is the target (n-1, m-1), return the current time as the answer.

7. Determine the duration of the next move (1 second if the current time parity is even, 2 seconds if odd).

8. For each adjacent room:

9. Compute the earliest time you can enter that room by taking the max of the next room’s moveTime and the current time plus the move duration.

10. Adjust for parity: if the difference between the arrival time and current time is odd when it needs to be even (or vice versa), increment time by 1 to preserve the alternating pattern.

11. If this new time is less than the previously recorded minTime for that room, update minTime and push it to the priority queue.

12. Return the minimum time recorded for (n-1, m-1).

Why it works: Dijkstra's algorithm guarantees the first time we reach a node with the smallest cumulative time is optimal, because we expand nodes in increasing order of arrival time. Adjusting for move alternation and moveTime ensures all constraints are respected.

Python Solution

from typing import List
import heapq

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        minTime = [[float('inf')] * m for _ in range(n)]
        minTime[0][0] = 0
        heap = [(0, 0, 0)]  # time, row, col
        
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        
        while heap:
            currTime, r, c = heapq.heappop(heap)
            if r == n - 1 and c == m - 1:
                return currTime
            if currTime > minTime[r][c]:
                continue
            stepTime = 1 if currTime % 2 == 0 else 2
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m:
                    nextTime = max(currTime + stepTime, moveTime[nr][nc])
                    if (nextTime - moveTime[r][c]) % 2 != stepTime % 2:
                        nextTime += 1
                    if nextTime < minTime[nr][nc]:
                        minTime[nr][nc] = nextTime
                        heapq.heappush(heap, (nextTime, nr, nc))

Explanation: We use a priority queue to always expand the room reachable in the minimum time. The step time alternates between 1 and 2 based on the parity of the current time. For each neighbor, we compute the earliest allowed arrival time using moveTime and ensure the step alternation is respected. If the new time is better than previously recorded, we push it onto the queue.

Go Solution

package main

import (
    "container/heap"
    "math"
)

type Item struct {
    time, r, c int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].time < pq[j].time }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minTimeToReach(moveTime [][]int) int {
    n, m := len(moveTime), len(moveTime[0])
    minTime := make([][]int, n)
    for i := range minTime {
        minTime[i] = make([]int, m)
        for j := range minTime[i] {
            minTime[i][j] = math.MaxInt64
        }
    }
    minTime[0][0] = 0
    pq := &PriorityQueue{{0, 0, 0}}
    heap.Init(pq)
    directions := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    
    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        currTime, r, c := item.time, item.r, item.c
        if r == n-1 && c == m-1 {
            return currTime
        }
        if currTime > minTime[r][c] {
            continue
        }
        stepTime := 1
        if currTime%2 == 1 {
            stepTime = 2
        }
        for _, d := range directions {
            nr, nc := r + d[0], c + d[1]
            if nr >= 0 && nr < n && nc >= 0 && nc < m {
                nextTime := currTime + stepTime
                if nextTime < moveTime[nr][nc] {
                    nextTime = moveTime[nr][nc]
                }
                if (nextTime - moveTime[r][c]) % 2 != stepTime % 2 {
                    nextTime += 1
                }
                if nextTime < minTime[nr][nc] {
                    minTime[nr][nc] = nextTime
                    heap.Push(pq, Item{nextTime, nr, nc})
                }
            }
        }
    }
    return -1