Problem Informations

Problem Index: 3342
Problem Link: Find Minimum Time to Reach Last Room II
Topics: Array, Graph, Heap (Priority Queue), Matrix, Shortest Path

Problem Description

There is a dungeon with $n \times m$ rooms arranged as a grid.

You are given a 2D array moveTime of size $n \times m$, where moveTime[i][j] represents the minimum time in seconds when you can start moving to that room. You start from the room $(0, 0)$ at time $t = 0$ and can move to an adjacent room. Moving between adjacent rooms takes one second for one move and two seconds for the next, alternating between the two.

Return the minimum time to reach the room $(n - 1, m - 1)$.

Two rooms are adjacent if they share a common wall, either horizontally or vertically.

Example 1:

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

Output: 7

Explanation:

The minimum time required is 7 seconds.

At time $t == 4$, move from room $(0, 0)$ to room $(1, 0)$ in one second.
At time $t == 5$, move from room $(1, 0)$ to room $(1, 1)$ in two seconds.

Example 2:

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

Output: 6

Explanation:

The minimum time required is 6 seconds.

At time $t == 0$, move from room $(0, 0)$ to room $(1, 0)$ in one second.
At time $t == 1$, move from room $(1, 0)$ to room $(1, 1)$ in two seconds.
At time $t == 3$, move from room $(1, 1)$ to room $(1, 2)$ in one second.
At time $t == 4$, move from room $(1, 2)$ to room $(1, 3)$ in two seconds.

Example 3:

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

Output: 4

Constraints:

$2 \leq n == moveTime.length \leq 750$
$2 \leq m == moveTime[i].length \leq 750$
$0 \leq moveTime[i][j] \leq 10^9$

Intuition

The problem asks us to determine the minimum time required to traverse from the top-left corner to the bottom-right corner of a grid with constraints on the time one can start moving into each cell and the alternation between one and two seconds required to move between adjacent cells. This problem can be interpreted as a graph traversal problem where each cell represents a node, and movement between nodes (cells) alternates in cost. It is analogous to finding the shortest path on a weighted graph with variable edge weights, which can be efficiently tackled using a variant of Dijkstra’s algorithm.

Approach

The approach leverages a priority queue-based traversal similar to Dijkstra’s algorithm to find the minimum time path across the grid. Here’s a breakdown of the steps involved:

Initialization:
- We maintain a 3D visited array to track states based on the cell coordinates and the parity of the step (whether the next move takes 1 or 2 seconds).
- A priority queue (min-heap) is employed to store states as tuples consisting of the negative time (to prioritize the smallest time when popped), current cell coordinates (row, column), and step parity (whether the next move takes 1 or 2 seconds).
Starting Point:
- We initiate the search at cell (0, 0) with zero time and even parity (next move takes 1 second).
Priority Queue Processing:
- The main loop continues until the priority queue is empty.
- For each state retrieved from the queue, we check if it has already been visited. If so, it’s skipped to prevent redundant calculations.
- If the target cell (n-1, m-1) is reached, the current time is returned as it represents the earliest possible time this cell can be visited, considering all constraints.
Exploration of Adjacent Cells:
- From the current cell, we attempt to move to each of its four adjacent cells (right, down, left, up).
- We ensure that any move stays within the grid bounds.
- The arrival_time to the new cell is calculated. It considers the maximum between the required moveTime to enter a cell and the current time plus the required move time (1 or 2 seconds depending on the parity).
- This new state is then pushed onto the priority queue for further exploration.
Termination:
- If the target cell (n-1, m-1) is reached, the calculated minimal time is returned immediately.
- If the priority queue is exhausted without reaching the target, this indicates the room is unreachable in any valid path, though this situation is constrained by problem guarantees. In such cases, -1 is returned.

This algorithm efficiently explores only necessary paths and ensures the minimum traversal time is used by prioritizing paths that offer earlier access to any cell. The alternate step timing is managed by alternating the parity and adapting the traversal cost accordingly.

Code

C++

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size(); // Number of rows
        int m = moveTime[0].size(); // Number of columns

        // 3D vector to keep track of visited states with parities 0 and 1
        vector<vector<vector<bool>>> visited(n, vector<vector<bool>>(m, vector<bool>(2, false)));

        // Directions for moving in the grid: right, down, left, up
        int moves[] = {1, 0, -1, 0, 1};

        // Min-heap (priority queue) to store states as tuples of (negative time, row, column, parity)
        priority_queue<tuple<int, int, int, int>> pq;
        pq.push({0, 0, 0, 0}); // Start from (0,0) with time 0 and parity 0

        while (!pq.empty()) {
            auto [neg_time, y, x, parity] = pq.top(); // Extract current state
            pq.pop();

            // If the current cell with its parity has been visited, skip processing
            if (visited[y][x][parity]) continue;
            visited[y][x][parity] = true; // Mark the current state as visited

            // If we reach the target cell (bottom-right corner), return the time
            if (y == n - 1 && x == m - 1) return -neg_time;

            // Explore adjacent cells
            for (int i = 0; i < 4; ++i) {
                int ny = y + moves[i]; // New row index
                int nx = x + moves[i + 1]; // New column index

                // Check if the new indices are within bounds
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

                // Calculate the arrival time to the new cell
                int arrival_time = max(-neg_time, moveTime[ny][nx]) + (parity == 0 ? 1 : 2);

                // Push the new state into the priority queue
                pq.push({-arrival_time, ny, nx, 1 - parity});
            }
        }

        return -1; // Return -1 if the target cell (n-1, m-1) is not reachable
    }
};

Python

class Solution:
    def minTimeToReach(self, moveTime):
        n = len(moveTime)  # Number of rows
        m = len(moveTime[0])  # Number of columns

        # 3D list to keep track of visited states with parities 0 and 1
        visited = [[[False, False] for _ in range(m)] for _ in range(n)]

        # Directions for moving in the grid: right, down, left, up
        moves = [1, 0, -1, 0, 1]

        # Min-heap (priority queue) to store states as tuples of (negative time, row, column, parity)
        from heapq import heappush, heappop
        pq = []
        heappush(pq, (0, 0, 0, 0))  # Start from (0,0) with time 0 and parity 0

        while pq:
            neg_time, y, x, parity = heappop(pq)  # Extract current state

            # If the current cell with its parity has been visited, skip processing
            if visited[y][x][parity]:
                continue
            visited[y][x][parity] = True  # Mark the current state as visited

            # If we reach the target cell (bottom-right corner), return the time
            if y == n - 1 and x == m - 1:
                return -neg_time

            # Explore adjacent cells
            for i in range(4):
                ny = y + moves[i]  # New row index
                nx = x + moves[i + 1]  # New column index

                # Check if the new indices are within bounds
                if ny < 0 or ny >= n or nx < 0 or nx >= m:
                    continue

                # Calculate the arrival time to the new cell
                arrival_time = max(-neg_time, moveTime[ny][nx]) + (1 if parity == 0 else 2)

                # Push the new state into the priority queue
                heappush(pq, (-arrival_time, ny, nx, 1 - parity))

        return -1  # Return -1 if the target cell (n-1, m-1) is not reachable

Complexity

Time complexity: $O(n \times m \times \log(n \times m))$
The algorithm utilizes a priority queue to explore the grid, treating it as a graph where each node (cell) has up to 4 neighbors. With $n \times m$ cells to consider, each push or pop operation on the priority queue (heap) takes $O(\log(n \times m))$ time. Thus, as each edge (move) is processed once, the overall time complexity is $O(n \times m \times \log(n \times m))$.
Space complexity: $O(n \times m)$
The space complexity is dominated by the visited 3D vector and priority queue storage requirements, maintaining state information for each grid cell. While each cell has two parity states stored, the overall space remains $O(n \times m)$. The priority queue could potentially hold $O(n \times m)$ elements as well, but its size is generally smaller due to the priority ordering.

CS Note
中

Leetcode 3342. Find Minimum Time to Reach Last Room II