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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Minimum Time to Reach Last Room I

Number: 3627

Difficulty: Medium

Paid? No

Companies: Uber

Problem Description

We are given an n x m grid where each cell (i, j) represents a room in a dungeon. The value moveTime[i][j] indicates the earliest time (in seconds) you’re allowed to start moving into that room. Starting at (0, 0) at time t = 0, you can move to any adjacent room (up, down, left, or right) in exactly 1 second. However, if you reach a room before its allowed moveTime, you must wait until that time before actually moving into it. The task is to compute the minimum time needed to reach the bottom-right room (n - 1, m - 1).

Key Insights

  • Model this as a shortest path problem on a grid where each move costs 1 second, but you might incur waiting time.
  • Use Dijkstra’s algorithm with a min-heap (priority queue) to efficiently track the earliest arrival times.
  • For each move, the effective arrival time at a neighbor is max(current time + 1, moveTime at the neighbor).
  • Avoid processing outdated routes by checking if a better time for a cell has already been found.

Space and Time Complexity

Time Complexity: O(n * m * log(n*m)) due to processing each cell with a min-heap. Space Complexity: O(n * m) for storing the distance (time) matrix.

Solution

We use a Dijkstra-like algorithm that leverages a min-heap (or priority queue) to always choose the room that can be reached the earliest. For each neighboring room, we calculate the new arrival time using 1 second for movement and possibly waiting until the room's moveTime if necessary. If this new time is better than the previously recorded time, we update and add the neighbor to our heap.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

import heapq

def minTimeToReachLastRoom(moveTime):
    n = len(moveTime)
    m = len(moveTime[0])
    
    # Directions for adjacent moves: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # Initialize distance matrix with infinity and set start (0,0)
    dist = [[float('inf')] * m for _ in range(n)]
    dist[0][0] = 0
    
    # Priority queue holding (current time, row, column)
    heap = [(0, 0, 0)]
    
    while heap:
        current_time, row, col = heapq.heappop(heap)
        
        # If destination is reached, return the current time
        if row == n - 1 and col == m - 1:
            return current_time
        
        # Skip if a better route to this cell is already known
        if current_time > dist[row][col]:
            continue
        
        # Explore adjacent cells
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < n and 0 <= new_col < m:
                # Calculate arrival time: moving takes 1 second and may require waiting
                next_time = max(current_time + 1, moveTime[new_row][new_col])
                if next_time < dist[new_row][new_col]:
                    dist[new_row][new_col] = next_time
                    heapq.heappush(heap, (next_time, new_row, new_col))
    return -1

# Example test case:
print(minTimeToReachLastRoom([[0,4],[4,4]]))  # Expected output: 6
← Back to All Questions