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
- 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.
- So a move to a neighbour arriving at
t + 1must be rounded up to at leastgrid[neighbour]with the same parity. - The rounding is
nt += ((grid - nt + 1) // 2) * 2. - A Dijkstra over
(time, r, c)gives the earliest arrival at each cell. - 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
gridwithout the parity step:ntcould land on the wrong parity. - Forgetting the
-1case: 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.