⚡Flashcard Drill➔
NeetCode #638LC-2577HardAdvanced Graphs
← Back to All Problems

#638 · #2577 · Minimum Time to Visit a Cell In a Grid(在网格图中访问一个格子的最少时间)

📌 Problem Statement & Constraints

You are given an m x n grid where grid[i][j] is the earliest time you may enter cell (i, j). You start at (0, 0) at time 0 and each move takes 1 second. You may not wait, but you may move back and forth. Return the minimum time to reach the bottom-right, or -1. Constraints: 2 <= m, n <= 1000, 0 <= grid[i][j] <= 10^5.

💡 Core Algorithmic Approaches

  1. You cannot wait, but moving back and forth wastes 2 seconds per cycle, so the arrival time at a cell has a fixed parity relative to the path length.
  2. So a move to a neighbour arriving at t + 1 must be rounded up to at least grid[neighbour] with the same parity.
  3. The rounding is nt += ((grid - nt + 1) // 2) * 2.
  4. A Dijkstra over (time, r, c) gives the earliest arrival at each cell.
  5. If both neighbours of the start require more than 1 second, the answer is -1.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        import heapq
        m, n = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1                      # cannot leave the start at time 1
        h = [(0, 0, 0)]
        seen = {(0, 0)}
        while h:
            t, r, c = heapq.heappop(h)
            if r == m - 1 and c == n - 1:
                return t
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    nt = t + 1
                    if nt < grid[nr][nc]:
                        # round up to grid value with the SAME parity as nt
                        nt += ((grid[nr][nc] - nt + 1) // 2) * 2
                    heapq.heappush(h, (nt, nr, nc))
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n log(m * n)): each cell is pushed once.
💾 Space Complexity
O(m * n) for the heap and the visited set.

⚠️ Interview Pitfalls & Follow-ups

  • Ignoring the parity constraint: without it, a cell could be entered at an impossible time.
  • Assuming you can wait in place: you cannot; back-and-forth movement is what allows the parity adjustment.
  • Rounding up to grid without the parity step: nt could land on the wrong parity.
  • Forgetting the -1 case: if both start neighbours require more than 1 second, the start is a dead end.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems