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 I

Difficulty: Medium

Problem Description

You are given a 2D array moveTime of size n x 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 exactly one second. Return the minimum time to reach the room (n - 1, m - 1).

Key Insights

  • The problem can be modeled as a graph where each room is a node and edges exist between adjacent rooms.
  • The moveTime array indicates when you can move into each room, which adds a layer of complexity to the movement.
  • A priority queue (min-heap) can be effectively used to explore the rooms based on the earliest possible time you can move to them.

Space and Time Complexity

Time Complexity: O(n * m * log(n * m)), where n is the number of rows and m is the number of columns, due to the use of a priority queue to explore rooms.
Space Complexity: O(n * m) for storing the minimum time to reach each room.

Solution

The solution uses Dijkstra's algorithm, adapted for a grid with a waiting time. A priority queue is utilized to always expand the least time-consuming path first. We maintain a min_time array to track the earliest time we can reach each room. Starting from the top-left corner, we explore all four possible directions (up, down, left, right) and update the times accordingly.

Code Solutions

import heapq

def min_time_to_reach_room(moveTime):
    n, m = len(moveTime), len(moveTime[0])
    min_time = [[float('inf')] * m for _ in range(n)]
    min_time[0][0] = 0
    
    pq = [(0, 0, 0)]  # (time, x, y)
    
    while pq:
        current_time, x, y = heapq.heappop(pq)
        
        if (x, y) == (n - 1, m - 1):
            return current_time
        
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < n and 0 <= ny < m:
                wait_time = max(0, moveTime[nx][ny] - (current_time + 1))
                new_time = current_time + 1 + wait_time
                
                if new_time < min_time[nx][ny]:
                    min_time[nx][ny] = new_time
                    heapq.heappush(pq, (new_time, nx, ny))
    
    return -1  # If unreachable
← Back to All Questions