We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Minimum Time to Reach Last Room II

Difficulty: Medium

Problem Description

Given a 2D array moveTime of size n x m, representing the minimum time in seconds when you can start moving to that room, determine the minimum time to reach the room (n - 1, m - 1) from the starting room (0, 0). Moving between adjacent rooms takes one second for one move and two seconds for the next, alternating between the two.

Key Insights

  • The grid represents a dungeon with rooms that can only be accessed at specific times.
  • Movement between rooms alternates in time cost: one second for one move, two seconds for the next.
  • The problem resembles finding the shortest path in a weighted graph, where weights change based on the time taken to move.
  • A priority queue (or min-heap) can be used to explore the rooms in order of the earliest time they can be reached.

Space and Time Complexity

Time Complexity: O(n * m * log(n * m))
Space Complexity: O(n * m)

Solution

The problem can be solved using a modified Dijkstra's algorithm. We maintain a priority queue to explore the rooms based on the earliest time they can be reached. For each room, we check its adjacent rooms and calculate the time to reach them, considering the moveTime constraints. The time taken to move alternates, so we must account for whether the current move is one or two seconds. We update the earliest reachable time for each adjacent room and continue until we reach the destination room (n - 1, m - 1).

Code Solutions

import heapq

def minimumTime(moveTime):
    n, m = len(moveTime), len(moveTime[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    pq = [(moveTime[0][0], 0, 0)]  # (time, x, y)
    earliest_time = [[float('inf')] * m for _ in range(n)]
    earliest_time[0][0] = moveTime[0][0]
    
    while pq:
        current_time, x, y = heapq.heappop(pq)
        
        if (x, y) == (n - 1, m - 1):
            return current_time
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                move_cost = 1 if (current_time - moveTime[x][y]) % 3 == 0 else 2
                next_time = max(current_time + move_cost, moveTime[nx][ny])
                if next_time < earliest_time[nx][ny]:
                    earliest_time[nx][ny] = next_time
                    heapq.heappush(pq, (next_time, nx, ny))
                    
    return -1  # This should not happen with valid input
← Back to All Questions