Watch 10 video solutions for Minimum Time to Visit a Cell In a Grid, a hard level problem involving Array, Breadth-First Search, Graph. This walkthrough by NeetCodeIO has 12,047 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].
You are standing in the top-left cell of the matrix in 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 in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.
Example 1:
Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]] Output: 7 Explanation: One of the paths that we can take is the following: - at t = 0, we are on the cell (0,0). - at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1. - at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2. - at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3. - at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4. - at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5. - at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6. - at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7. The final time is 7. It can be shown that it is the minimum time possible.
Example 2:
Input: grid = [[0,2,4],[3,2,1],[1,0,4]] Output: -1 Explanation: There is no path from the top left to the bottom-right cell.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1050 <= grid[i][j] <= 105grid[0][0] == 0
Problem Overview: You are given a grid where grid[i][j] represents the earliest time you can enter that cell. Starting at the top-left cell, you move in four directions and each move costs one second. The goal is to reach the bottom-right cell in the minimum possible time while respecting each cell's time constraint.
Approach 1: Priority Queue with Dijkstra-Like Approach (O(mn log(mn)))
This problem behaves like a shortest path search on a weighted grid. Treat every cell as a node and each movement as an edge with cost 1, but you may need to wait before entering a cell if its allowed time hasn't been reached. Use a min-heap (priority queue) to always expand the position with the smallest current time, similar to Dijkstra’s algorithm. When exploring a neighbor, compute the earliest time you can step into it; if your arrival time is earlier than grid[r][c], you must wait, and parity adjustments may be required to ensure movement timing works with alternating steps.
The priority queue ensures cells are processed in increasing time order, guaranteeing the first time you reach the destination is optimal. Maintain a visited or distance matrix to avoid redundant processing. Time complexity is O(mn log(mn)) because each cell may be pushed into the heap and heap operations cost logarithmic time. Space complexity is O(mn) for the heap and distance tracking. This technique is a classic application of graph shortest path combined with a priority queue on a matrix.
Approach 2: Breadth-First Search with Level Traversal (O(mn))
A modified BFS can also traverse the grid while tracking time levels. Instead of simple layer expansion, you compute the earliest valid time to enter each neighbor and adjust the traversal level accordingly. If the neighbor's required time is larger than your next step, you simulate waiting by increasing the effective time until the move becomes valid. This sometimes introduces parity adjustments similar to the Dijkstra solution.
BFS works because all moves have uniform cost, but managing waiting times and revisiting states makes the implementation trickier. A queue processes states in increasing time order while storing the earliest reachable time for each cell. With proper pruning, each cell is processed only a limited number of times. Time complexity is approximately O(mn) with O(mn) space for the queue and visitation tracking. This approach emphasizes traversal mechanics from Breadth-First Search but requires careful time calculations.
Recommended for interviews: The Dijkstra-style priority queue approach is what most interviewers expect. The grid naturally forms a weighted graph where arrival time matters, making a min-heap the most intuitive and reliable solution. Mentioning BFS first shows you recognize the grid traversal pattern, but switching to a heap-based shortest path demonstrates stronger algorithmic judgment.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Priority Queue with Dijkstra-Like Approach | O(mn log(mn)) | O(mn) | Best general solution for shortest path with time constraints. Reliable and commonly expected in interviews. |
| Breadth-First Search with Level Traversal | O(mn) | O(mn) | Useful when modeling traversal levels directly and handling wait times carefully. |