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

Minimum Time to Visit a Cell In a Grid

Number: 2711

Difficulty: Hard

Paid? No

Companies: Google, Microsoft, Atlassian

Problem Description

You are given an m x n matrix called grid where grid[row][col] is the minimum time required for that cell (row, col) to be “open” for visiting. You start at the top‐left cell at time 0 and must move in one of the four directions (up, down, left, right) with each move costing exactly 1 second. However, you can only move into an adjacent cell if your arrival time is at least the value given in that cell. Because you cannot remain idle in any cell (i.e. you must move every second) the only way to “wait” and let time pass is to take a detour (for example, leaving a cell and revisiting it later) to effectively delay your arrival. The goal is to determine the minimum time required to reach the bottom‐right cell. If no valid path exists, return -1.

Key Insights

  • The grid defines not only movement but also time restrictions for when a cell can be visited.
  • Since moves are constrained to adjacent cells and each move costs 1 second (with “waiting” only possible via cycles in the grid), this naturally forms a weighted graph with time as the cost.
  • A shortest-path algorithm (Dijkstra’s algorithm) using a min-heap (priority queue) can be used to determine the minimum arrival time.
  • When moving from a cell at time t to a neighbor, if t+1 is less than the neighbor’s threshold, you cannot “wait” in place. Instead, you must take extra moves (a detour cycle) to effectively increment the time. The key observation is that any detour adds time in increments of 2 seconds. Thus, if t+1 < grid[nr][nc], then define temp = grid[nr][nc] - t. The smallest odd number k ≥ temp is used so that arrival time = t+k. In other words, if temp is odd use k=temp; if even, use k=temp+1.
  • This parity adjustment is the “gotcha” in the problem.

Space and Time Complexity

Time Complexity: O(mn * log(mn)) – each cell is processed at most once in the min-heap. Space Complexity: O(m*n) – storing the distance/time for each cell plus the min-heap size.

Solution

We solve the problem by modeling the grid as a graph where each cell is a node and edges exist between adjacent cells with a traversal cost of 1 second. However, when the candidate arrival time (current time + 1) is less than the required time for the neighbor, we must “wait” by taking a detour (which adds an extra second for every two moves). The adjustment is determined by computing:   temp = grid[nr][nc] - current_time. If current_time + 1 is less than grid[nr][nc], then we set:   if (temp) is odd → newTime = current_time + temp,   if (temp) is even → newTime = current_time + temp + 1. Otherwise, we simply set newTime = current_time + 1. Using a priority queue (min-heap), we perform Dijkstra’s algorithm to propagate the minimum arrival times and finally return the arrival time for the bottom-right cell (or -1 if it is unreachable).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. Each solution is commented line by line.

import heapq

def minimumTime(grid):
    m, n = len(grid), len(grid[0])
    # Directions for up, down, left, right
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    # 2D array to record minimum time to reach each cell; initialize with infinity
    dist = [[float('inf')] * n for _ in range(m)]
    dist[0][0] = 0
    # Priority queue for Dijkstra: (current_time, row, col)
    heap = [(0, 0, 0)]
    
    while heap:
        cur_time, r, c = heapq.heappop(heap)
        # If we have reached bottom-right, return the time
        if r == m - 1 and c == n - 1:
            return cur_time
        # Skip if we have already found a better time for this cell
        if cur_time > dist[r][c]:
            continue
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check bounds
            if 0 <= nr < m and 0 <= nc < n:
                candidate = cur_time + 1
                # If candidate time meets neighbor's cell requirement
                if candidate >= grid[nr][nc]:
                    new_time = candidate
                else:
                    # Calculate waiting: we need the smallest odd number k so that cur_time+k >= grid[nr][nc]
                    diff = grid[nr][nc] - cur_time
                    # diff must be odd to be reachable because moves alternate parity
                    if diff % 2 == 1:
                        new_time = cur_time + diff
                    else:
                        new_time = cur_time + diff + 1
                # Update if a better time is found for the neighbor cell
                if new_time < dist[nr][nc]:
                    dist[nr][nc] = new_time
                    heapq.heappush(heap, (new_time, nr, nc))
                    
    return -1

# Example usage:
# grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
# print(minimumTime(grid))  # Expected output: 7
← Back to All Questions