Facebook Pixel

3342. Find Minimum Time to Reach Last Room II

MediumGraphArrayMatrixShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

You are given a dungeon consisting of n x m rooms arranged in a grid pattern. This grid is represented by a 2D array called moveTime, where each element moveTime[i][j] specifies the earliest time in seconds when you can begin moving to room (i, j).

Starting from the top-left room (0, 0) at time t = 0, you can traverse to any adjacent room either horizontally or vertically. The movement between adjacent rooms alternates in time: the first move takes one second, the second move takes two seconds, the third move one second, and so on, continuing this alternating pattern.

The task is to find the minimum time required to reach the bottom-right room (n - 1, m - 1) from the starting point.

Intuition

To solve this problem, we can use Dijkstra's algorithm, a classic graph search approach that is well-suited for finding the shortest paths in weighted graphs. Here, the grid of rooms can be thought of as a graph where each room is a node and each direct path between adjacent rooms is an edge with a weight according to the time conditions given.

  1. Data Structures: Start by initializing a 2D array dist where dist[i][j] tracks the minimum time to reach room (i, j). Initialize all values in dist to represent infinity, except the starting room (0, 0), which is set to 0.

  2. Priority Queue: Use a priority queue (or min-heap) to keep track of the rooms to explore, starting with the initial room (0, 0) at time 0.

  3. Explore Rooms: For each room explored via the queue:

    • If it's the destination room (n - 1, m - 1), return the time as it's the minimum time found.
    • Otherwise, consider all adjacent rooms. For each adjacent room:
      • Check the minimum time needed to move there, factoring in both the move time conditions and the earliest time you can arrive at the new room.
      • If the computed time to reach an adjacent room is less than the current stored time (dist[x][y]), update dist[x][y] and enqueue this new room with the updated time.

This approach ensures that all room explorations are done in the order of the minimum time, akin to exploring the shortest paths, leading to an efficient solution.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution employs Dijkstra's algorithm, an efficient method for finding the shortest paths in graphs where edge weights are non-negative. In this problem, we treat the grid of rooms like a graph, where each room represents a node and movements between rooms are directed edges with dynamic weights.

Step-by-Step Implementation:

  1. Initialize Structures:

    • Create a 2D array dist of the same size as moveTime, filled initially with inf (infinity) to indicate unreachable states. Set dist[0][0] to 0 because you start at time 0.
    • Utilize a priority queue pq to facilitate exploring the closest next room based on time. Start by adding the tuple (0, 0, 0) to signify the room at (0, 0) can be reached in 0 seconds.

  2. Direction Vectors:

    • Use dirs = (-1, 0, 1, 0, -1) to easily access the four potential adjacent rooms: left, up, right, and down.

  3. Processing Loop:

    • While processing the priority queue, pop the room (d, i, j) that has the smallest time d from the queue.
    • If the current room is the target (n - 1, m - 1), return d as it represents the minimum time to reach this room.
    • Skip further processing if d (current time) exceeds dist[i][j] since a quicker path has already been found.

  4. Explore Neighbors:

    • For each neighbor (x, y) of (i, j), ensure x and y are within bounds.
    • Calculate the travel time t, which is the larger of the current movement time or the earliest permitted move time moveTime[x][y], plus the oscillating step time (i + j) % 2 + 1.
    • If dist[x][y] can be minimized with t, update dist[x][y] and enqueue (t, x, y) into the priority queue.

By systematically applying Dijkstra's algorithm, this solution ensures that all room transitions respect the time constraints and finds the fastest path to reach the destination, thereby solving the problem optimally.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small 3x3 dungeon grid represented by the moveTime array to illustrate the solution approach:

moveTime = [
    [0, 2, 3],
    [1, 4, 5],
    [2, 6, 7]
]

The goal is to find the minimum time to travel from the top-left corner (0, 0) to the bottom-right corner (2, 2), starting at t = 0.

Step-by-Step Execution:

  1. Initialization:

    • Initialize dist as a 3x3 grid with infinity: 
      dist = [
    [0, inf, inf],
    [inf, inf, inf],
    [inf, inf, inf]
]
    • Initialize a priority queue pq with the tuple (0, 0, 0) representing room (0, 0) reached in 0 seconds.

  2. Process Room (0, 0):

    • Pop (0, 0, 0) from the queue.
    • Current time d = 0, position (i, j) = (0, 0).
    • Consider moving to adjacent rooms (0, 1) and (1, 0).
      • Room (0, 1):
        • Calculate movement time: max(2, 0) + 1 = 3 (since moveTime[0][1] = 2 and the next move costs 1 second).
        • Update and push: dist[0][1] = 3; enqueue (3, 0, 1).
      • Room (1, 0):
        • Calculate movement time: max(1, 0) + 1 = 2.
        • Update and push: dist[1][0] = 2; enqueue (2, 1, 0).

  3. Process Room (1, 0):

    • Pop (2, 1, 0) from the queue.
    • Current time d = 2, position (i, j) = (1, 0).
    • Consider moving to (0, 0), (1, 1), and (2, 0).
      • Rooms (0, 0) and (2, 0) are confirmed to have higher or equal times.
      • Room (1, 1):
        • Calculate movement time: max(4, 2) + 2 = 6.
        • Update and push: dist[1][1] = 6; enqueue (6, 1, 1).

  4. Process Room (0, 1):

    • Pop (3, 0, 1) from the queue.
    • Current time d = 3, position (i, j) = (0, 1).
    • Consider moving to (0, 0), (0, 2), and (1, 1).
      • Room (0, 0) observed to have higher time.
      • Room (0, 2):
        • Calculate movement time: max(3, 3) + 2 = 5.
        • Update and push: dist[0][2] = 5; enqueue (5, 0, 2).
      • Room (1, 1) can be reached faster through existing queued paths.

  5. Process Rooms (0, 2), `[(5, 0, 2)], (1, 1), [(6, 1, 1)], and so on...**:

    • Continue processing these rooms, verifying all reachable paths and updating distances as calculated.

  6. Final Target Reach:

    • Eventually, reach (2, 2) with the minimum time found using these updates, let's say it's with a time of 8.

The described process exemplifies using the grid pattern of Dijkstra's algorithm to ensure the path selected is optimal against alternative routes based on movement timing. This illustrates how the algorithm efficiently identifies the quickest route under specified conditions.

Solution Implementation

1from heapq import heappop, heappush
2from itertools import pairwise
3from typing import List
4from math import inf
5
6class Solution:
7    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
8        # Number of rows and columns
9        n, m = len(moveTime), len(moveTime[0])
10      
11        # Initialize distance matrix with infinity. Start point is set to 0.
12        dist = [[inf] * m for _ in range(n)]
13        dist[0][0] = 0
14      
15        # Priority queue to hold the current minimum times with their coordinates
16        pq = [(0, 0, 0)] # starting point with time 0
17      
18        # Directions for moving up, right, down, left (useful for grid traversal)
19        dirs = (-1, 0, 1, 0, -1)
20      
21        while pq:
22            # Extract the position with the smallest current distance
23            d, i, j = heappop(pq)
24          
25            # If the destination is reached, return the distance
26            if i == n - 1 and j == m - 1:
27                return d
28          
29            # Ignore if a better path is already calculated
30            if d > dist[i][j]:
31                continue
32          
33            # Explore neighbors (adjacent cells)
34            for a, b in pairwise(dirs):
35                x, y = i + a, j + b
36                # Check if new coordinates are within bounds
37                if 0 <= x < n and 0 <= y < m:
38                    # New time is the greater of either the given cell's moving time
39                    # or the currently calculated time plus a constant based on parity of coordinates.
40                    t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1
41                    # If a shorter time is found to reach this cell, update and push to priority queue
42                    if dist[x][y] > t:
43                        dist[x][y] = t
44                        heappush(pq, (t, x, y))
45
1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4class Solution {
5
6    public int minTimeToReach(int[][] moveTime) {
7        // Get the dimensions of the moveTime matrix.
8        int rows = moveTime.length;
9        int cols = moveTime[0].length;
10
11        // Initialize distance matrix with maximum values.
12        int[][] distance = new int[rows][cols];
13        for (var row : distance) {
14            Arrays.fill(row, Integer.MAX_VALUE);
15        }
16        // Starting point has a distance of 0.
17        distance[0][0] = 0;
18
19        // PriorityQueue to hold {total time, row index, column index}.
20        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
21        // Add starting point to the queue.
22        priorityQueue.offer(new int[] {0, 0, 0});
23
24        // Directions for moving up, right, down, and left.
25        int[] directions = {-1, 0, 1, 0, -1};
26
27        while (!priorityQueue.isEmpty()) {
28            // Get the node with the smallest total time.
29            int[] current = priorityQueue.poll();
30            int currentTime = current[0];
31            int currentRow = current[1];
32            int currentCol = current[2];
33
34            // If the end of the grid is reached, return the total time.
35            if (currentRow == rows - 1 && currentCol == cols - 1) {
36                return currentTime;
37            }
38
39            // If the current time is not better than the stored distance, skip.
40            if (currentTime > distance[currentRow][currentCol]) {
41                continue;
42            }
43
44            // Explore all possible directions.
45            for (int k = 0; k < 4; k++) {
46                int newRow = currentRow + directions[k];
47                int newCol = currentCol + directions[k + 1];
48
49                // Check if the new position is within bounds.
50                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
51                    // Calculate the new time needed to reach this position.
52                    int newTime = Math.max(moveTime[newRow][newCol], distance[currentRow][currentCol]) + (currentRow + currentCol) % 2 + 1;
53
54                    // If a better time is found, update and add it to the queue.
55                    if (distance[newRow][newCol] > newTime) {
56                        distance[newRow][newCol] = newTime;
57                        priorityQueue.offer(new int[] {newTime, newRow, newCol});
58                    }
59                }
60            }
61        }
62      
63        // In case no path is found, though based on problem constraints it should never reach here.
64        return Integer.MAX_VALUE;
65    }
66}
67
1#include <vector>
2#include <queue>
3#include <array>
4#include <limits.h>
5
6using namespace std;
7
8class Solution {
9public:
10    int minTimeToReach(vector<vector<int>>& moveTime) {
11        int n = moveTime.size(); // Number of rows
12        int m = moveTime[0].size(); // Number of columns
13      
14        // Distance matrix to record minimum times to reach each cell, initialized to INT_MAX
15        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
16        dist[0][0] = 0; // Starting point's time is zero
17
18        // Priority queue to implement Dijkstra's algorithm, stores {distance, row, column}
19        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> priorityQueue;
20        priorityQueue.push({0, 0, 0}); // Starting point pushed with time 0
21
22        // Direction vectors for moving: up, right, down, left (and wrap around for row/column calculations)
23        int directions[5] = {-1, 0, 1, 0, -1};
24
25        while (!priorityQueue.empty()) {
26            auto [currentDist, row, col] = priorityQueue.top(); // Get the element with the smallest distance
27            priorityQueue.pop();
28
29            // If we reached the bottom right corner, return the time
30            if (row == n - 1 && col == m - 1) {
31                return currentDist;
32            }
33
34            // If current distance is greater than recorded distance, continue
35            if (currentDist > dist[row][col]) {
36                continue;
37            }
38
39            // Explore the four possible directions
40            for (int k = 0; k < 4; ++k) {
41                int newRow = row + directions[k];
42                int newCol = col + directions[k + 1];
43
44                // Check boundaries
45                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {
46                    // Calculate time to move to the new cell
47                    int newTime = max(moveTime[newRow][newCol], dist[row][col]) + (row + col) % 2 + 1;
48
49                    // If a faster time is found, update and push into the priorityQueue
50                    if (dist[newRow][newCol] > newTime) {
51                        dist[newRow][newCol] = newTime;
52                        priorityQueue.push({newTime, newRow, newCol});
53                    }
54                }
55            }
56        }
57        return -1; // This line should never be reached as we expect to find a path
58    }
59};
60
1// Function to calculate the minimum time to reach the bottom-right corner of a grid
2function minTimeToReach(moveTime: number[][]): number {
3    const [n, m] = [moveTime.length, moveTime[0].length]; // Dimensions of the grid
4    const dist: number[][] = Array.from({ length: n }, () => Array(m).fill(Infinity)); // Distance array initialized to Infinity
5    dist[0][0] = 0; // Starting point set to distance 0
6
7    // Priority queue to process nodes in order of shortest distance first
8    const pq = new PriorityQueue({ compare: (a, b) => a[0] - b[0] });
9    pq.enqueue([0, 0, 0]); // Enqueue starting point with distance 0
10  
11    // Direction vectors for moving up, right, down, left
12    const directions = [-1, 0, 1, 0, -1];
13
14    while (true) {
15        const [currentDist, x, y] = pq.dequeue(); // Dequeue element with the smallest distance
16        if (x === n - 1 && y === m - 1) {
17            return currentDist; // Reached destination, return the distance
18        }
19        if (currentDist > dist[x][y]) {
20            continue; // If current distance is not better, skip processing
21        }
22        for (let k = 0; k < 4; ++k) {
23            const [newX, newY] = [x + directions[k], y + directions[k + 1]]; // Calculate new position
24            if (newX >= 0 && newX < n && newY >= 0 && newY < m) { // Check boundaries
25                // Calculate potential new time to reach this cell
26                const newTime = Math.max(moveTime[newX][newY], dist[x][y]) + ((x + y) % 2) + 1;
27                if (dist[newX][newY] > newTime) { // Check if new time is better
28                    dist[newX][newY] = newTime; // Update distance
29                    pq.enqueue([newTime, newX, newY]); // Enqueue updated distance and position
30                }
31            }
32        }
33    }
34}
35
36// Placeholder for the priority queue, assuming an existing implementation
37declare class PriorityQueue<T> {
38    constructor(options: { compare: (a: T, b: T) => number });
39    enqueue(item: T): void;
40    dequeue(): T;
41}
42

Time and Space Complexity

The time complexity of the code is O(n \times m \times \log (n \times m)). This complexity arises from the use of a priority queue where each cell of the grid can be enqueued and dequeued, leading to a logarithmic factor with respect to the number of grid cells, which is n \times m.

The space complexity is O(n \times m). This stems from storing the dist array, which maintains the minimum time to reach each cell in the moveTime grid. Additionally, the priority queue's space usage is also bounded by O(n \times m).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these properties could exist for a graph but not a tree?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Shortest Path

Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More