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

Minimum Time to Visit a Cell In a Grid

Difficulty: Hard

Problem Description

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col). You are standing in the top-left cell of the matrix at the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second. Return the minimum time required to visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, return -1.

Key Insights

  • Each cell has a time constraint that must be satisfied before visiting.
  • Movement to adjacent cells takes 1 second, which adds to the total time.
  • A path must be found that satisfies both the movement time and the cell visit time constraints.
  • A graph traversal algorithm, such as BFS or Dijkstra's, can be used to find the shortest path considering these constraints.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)) - due to the priority queue operations for pathfinding. Space Complexity: O(m * n) - for storing the visited states and the priority queue.

Solution

The problem can be approached using a modified Dijkstra's algorithm, where the nodes are the cells in the grid, and the edges represent the possible moves to adjacent cells. The priority queue will help manage which cell to visit next based on the minimum time required to enter that cell.

  1. Initialize a priority queue and push the starting cell (0, 0) with time 0.
  2. Maintain a 2D array to track the minimum time required to reach each cell.
  3. While the priority queue is not empty:
    • Extract the cell with the minimum time.
    • If the bottom-right cell is reached, return the time.
    • Explore the valid adjacent cells and calculate the time needed to visit them based on the current time and the cell's constraints.
    • If the new calculated time is less than the recorded time for that cell, update it and push the new state to the priority queue.
  4. If the bottom-right cell cannot be reached, return -1.

Code Solutions

import heapq

def minimumTime(grid):
    m, n = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    min_time = [[float('inf')] * n for _ in range(m)]
    min_time[0][0] = 0
    pq = [(0, 0, 0)]  # (time, row, col)

    while pq:
        time, x, y = heapq.heappop(pq)

        if x == m - 1 and y == n - 1:
            return time

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                wait_time = max(0, grid[nx][ny] - (time + 1))
                new_time = 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
← Back to All Questions