LeetCode 3341 - Find Minimum Time to Reach Last Room I

LeetCode Problem 3341

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

Solution

Problem Understanding

The problem is asking for the minimum time required to reach the bottom-right room (n - 1, m - 1) in a dungeon represented as an n x m grid. Each room (i, j) has a moveTime[i][j], which specifies the earliest time at which the room can be entered. You start at (0, 0) at time t = 0 and can move to adjacent rooms (up, down, left, right), taking exactly one second per move. The challenge is to compute the minimum time to reach the final room while respecting the moveTime constraints.

The input consists of a 2D integer array, where n and m are both between 2 and 50. The move times can be large, up to 10^9, so a naive solution that simulates every second is impractical. The output is a single integer representing the earliest time you can arrive at (n - 1, m - 1).

Important considerations include handling rooms that are initially inaccessible due to their moveTime and ensuring moves are only made when a room is open. Edge cases to watch for include rooms that require waiting before entering, very small grids (2x2), and paths where detours are required to respect timing constraints.

Approaches

The brute-force approach would simulate movement second by second, checking which rooms are available at each time and exploring all possible paths. This could involve a BFS that tracks current time and available rooms. While correct, this approach can be extremely slow because the maximum moveTime can be 10^9, and the BFS would require infeasible computation and memory.

The optimal approach treats this as a shortest-path problem with time constraints, which is naturally solved using a priority queue (min-heap) combined with Dijkstra’s algorithm. Each state is defined by the position (i, j) and the earliest time you can arrive at that room. From a room (i, j) at time t_curr, moving to an adjacent room (ni, nj) will take one second, but you may have to wait if t_curr + 1 < moveTime[ni][nj]. Using a min-heap ensures we always expand the room that can be reached at the earliest time, guaranteeing correctness.

Algorithm Walkthrough

1. Initialize a min-heap (priority queue) with the starting room (0, 0) and time t = 0.
2. Create a 2D array visited or earliestTime of size n x m to store the minimum time at which each room is reached. Initialize all cells with infinity except (0, 0) which is 0.
3. Define the possible moves as (dx, dy) pairs: right, left, down, up.
4. While the heap is not empty, pop the room with the smallest current time t_curr.
5. For each adjacent room (ni, nj):

a. Compute next_time = t_curr + 1 because moving takes one second.

b. If next_time < moveTime[ni][nj], set next_time = moveTime[ni][nj] to wait until the room opens.

c. If next_time is smaller than the previously recorded time for (ni, nj), update earliestTime[ni][nj] and push (next_time, ni, nj) into the heap. 6. Repeat until the heap is empty or until (n - 1, m - 1) is reached. 7. Return earliestTime[n - 1][m - 1] as the minimum time to reach the last room.

Why it works: Using a min-heap guarantees that we always expand the room reachable at the earliest time. Waiting for a room to open is explicitly handled by comparing current time and moveTime, ensuring the algorithm respects the dungeon's timing constraints. Since each cell is expanded only when a smaller arrival time is found, this avoids unnecessary revisits and guarantees the optimal solution.

Python Solution

from heapq import heappush, heappop
from typing import List

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        earliestTime = [[float('inf')] * m for _ in range(n)]
        earliestTime[0][0] = 0
        heap = [(0, 0, 0)]  # (time, row, col)
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        
        while heap:
            t_curr, i, j = heappop(heap)
            if (i, j) == (n-1, m-1):
                return t_curr
            if t_curr > earliestTime[i][j]:
                continue
            for dx, dy in directions:
                ni, nj = i + dx, j + dy
                if 0 <= ni < n and 0 <= nj < m:
                    next_time = max(t_curr + 1, moveTime[ni][nj])
                    if next_time < earliestTime[ni][nj]:
                        earliestTime[ni][nj] = next_time
                        heappush(heap, (next_time, ni, nj))
        return earliestTime[n-1][m-1]

Explanation: We initialize a min-heap with (0, 0, 0) representing time and coordinates. earliestTime stores the minimum time at which each cell is reached. For each popped cell, we examine all four directions, calculate the next reachable time considering potential waits, update if it is better than the previously recorded time, and push into the heap. The function returns immediately when the last room is popped from the heap, guaranteeing the earliest time.

Go Solution

package main

import (
    "container/heap"
    "math"
)

type State struct {
    time, row, col int
}

type PriorityQueue []State

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.(State)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func minTimeToReach(moveTime [][]int) int {
    n, m := len(moveTime), len(moveTime[0])
    earliestTime := make([][]int, n)
    for i := range earliestTime {
        earliestTime[i] = make([]int, m)
        for j := range earliestTime[i] {
            earliestTime[i][j] = math.MaxInt64
        }
    }
    earliestTime[0][0] = 0
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, State{0, 0, 0})
    directions := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    
    for pq.Len() > 0 {
        curr := heap.Pop(pq).(State)
        t_curr, i, j := curr.time, curr.row, curr.col
        if i == n-1 && j == m-1 {
            return t_curr
        }
        if t_curr > earliestTime[i][j] {
            continue
        }
        for _, d := range directions {
            ni, nj := i + d[0], j + d[1]
            if ni >= 0 && ni < n && nj >= 0 && nj < m {
                next_time := t_curr + 1
                if next_time < moveTime[ni][nj] {
                    next_time = moveTime[ni][nj]
                }
                if next_time < earliestTime[ni][nj] {
                    earliestTime[ni][nj] = next_time
                    heap.Push(pq, State{next_time, ni, nj})
                }
            }
        }
    }
    return earliestTime[n-1][m-1]
}

Explanation: The Go implementation mirrors the Python solution using a priority queue. We define a State struct for each room, implement the heap interface, and track the earliest time for each room. Go requires explicit heap initialization and interface implementation, but the core algorithm and logic are identical.

Worked Examples

Example 1: moveTime = [[0,4],[4,4]]