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 II

Number: 3628

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given an n x m grid where each cell (i, j) has a moveTime value that represents the earliest time you are allowed to start moving into that room. Starting at room (0, 0) at time t = 0, you must reach room (n - 1, m - 1) by moving to an adjacent room (sharing a common wall). The twist is that the time cost for moves alternates: the first move takes 1 second, the second move takes 2 seconds, then 1 second, and so on. Determine the minimum time required to reach the destination while respecting the moveTime constraints.

Key Insights

  • The problem can be modeled as a graph traversal where each state is defined by the room coordinates (r, c) and the parity (even or odd move count) indicating whether the next move costs 1 second (even) or 2 seconds (odd).
  • Dijkstra's algorithm is well-suited because the waiting time (if the move is attempted before the allowed moveTime) and the alternating move durations create weighted edges.
  • Each state transition (to an adjacent room) computes the next available time by taking the maximum between the current time and the allowed move time, then adding the required move duration.
  • The grid has up to about 750x750 cells, and each cell has two states (depending on parity), so efficiency in both time and space is crucial.

Space and Time Complexity

Time Complexity: O(nmlog(nm)) – each state (cell with parity) is processed using a priority queue. Space Complexity: O(nm) – to store the minimum time required to reach each state.

Solution

We use Dijkstra's algorithm to traverse the grid where the state is represented by (row, column, parity). The parity indicates whether the next move takes 1 second (when parity == 0) or 2 seconds (when parity == 1). For each move:

  • Check each adjacent cell.
  • Wait until the moveTime for that cell if necessary.
  • Add 1 or 2 seconds based on the current parity.
  • Switch the parity for the next move. We maintain a priority queue (min-heap) to always process the state with the smallest current time, ensuring the optimal solution is found. Edge updating is done when a better (smaller time) state is found.

Code Solutions

import heapq

def minimumTime(moveTime):
    n, m = len(moveTime), len(moveTime[0])
    # Initialize a large value for all states (row, col, parity)
    INF = float('inf')
    # dist[r][c][parity]: minimum time to reach (r,c) with given parity state
    dist = [[[INF, INF] for _ in range(m)] for _ in range(n)]
    # Start at (0, 0) with parity 0 meaning the next move cost is 1
    dist[0][0][0] = 0
    heap = [(0, 0, 0, 0)]  # (current time, row, col, parity)
    
    # Valid directions: up, down, left, right
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    while heap:
        curr_time, r, c, parity = heapq.heappop(heap)
        # If we already found a shorter way to this state, skip it
        if curr_time > dist[r][c][parity]:
            continue
        
        # If this is the destination (n-1, m-1), we can return answer
        if r == n-1 and c == m-1:
            return curr_time
        
        # Explore adjacent cells
        next_move_cost = 1 if parity == 0 else 2
        next_parity = 1 - parity
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check bounds
            if 0 <= nr < n and 0 <= nc < m:
                # Wait until the allowed time for next room if needed
                start_time = max(curr_time, moveTime[nr][nc])
                arrival_time = start_time + next_move_cost
                if arrival_time < dist[nr][nc][next_parity]:
                    dist[nr][nc][next_parity] = arrival_time
                    heapq.heappush(heap, (arrival_time, nr, nc, next_parity))
    return -1  # if destination is unreachable

# Example usage:
print(minimumTime([[0,4],[4,4]]))  # Expected output: 7
← Back to All Questions