Minimum Time to Visit a Cell In a Grid
Minimum Time to Visit a Cell In a Grid is a hard graphs problem solved with the dijkstra pattern.
The best approach, optimal (dijkstra with parity-aware waiting), runs in O(m · n · log(m · n)) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from simulate second by second up.
Problem
You are given an m x n grid of non-negative integers. grid[r][c] is the earliest time at which cell (r, c) may be entered: you can be on that cell only at a time t >= grid[r][c].
You start on the top-left cell (0, 0) at time 0. Every second you must move to one of the four adjacent cells (up, down, left or right); standing still is not allowed. Each move takes exactly one second.
Return the earliest time at which you can stand on the bottom-right cell (m - 1, n - 1), or -1 if it can never be reached.
Examples
Example 1
- Input
grid = [[0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6]]- Output
7- Why
- Go (0,0) → (0,1) → (1,1) → (1,2) → (0,2) → (0,3) → (1,3) → (2,3), arriving at times 1 to 7; every cell's opening time is met on arrival.
Example 2
- Input
grid = [[0, 2], [3, 1]]- Output
-1- Why
- At time 1 both neighbours of the start are still closed, and you are not allowed to stand still, so you are stuck.
Example 3
- Input
grid = [[0, 1], [9, 4]]- Output
4- Why
- Reach (0,1) at time 1, step back to (0,0) at 2 and to (0,1) again at 3, then enter (1,1) at time 4.
Constraints
m == grid.length,n == grid[i].length,2 <= m, n <= 1000,4 <= m * n <= 10^50 <= grid[i][j] <= 10^5grid[0][0] == 0
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Simulate second by second | O(T · m · n) | O(m · n) |
| Optimal (Dijkstra with parity-aware waiting) | O(m · n · log(m · n)) | O(m · n) |
1Simulate second by second
O(T · m · n)T is the answer, which can reach about max(grid) + m + n, and each second rescans the whole grid.O(m · n)Two boolean grids for the current and next second.Keep the set of cells you could be standing on at time t. The set for t + 1 is every neighbour of those cells whose opening time is at most t + 1. The first t whose set contains the bottom-right cell is the answer. If the first move is impossible, answer -1 straight away; otherwise the target is always reached.
- If
grid[0][1] > 1andgrid[1][0] > 1, return -1. cur= {(0, 0)} att = 0.- Repeat: if the target is in
cur, returnt; buildnextfrom neighbours withgrid <= t + 1;t++.
class Solution {
public int minimumTime(int[][] grid) {
int m = grid.length, n = grid[0].length;
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
boolean[][] cur = new boolean[m][n];
cur[0][0] = true;
for (int t = 0; ; t++) {
if (cur[m - 1][n - 1]) return t;
boolean[][] next = new boolean[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (!cur[r][c]) continue;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] <= t + 1) next[nr][nc] = true;
}
}
}
cur = next;
}
}
}class Solution:
def minimumTime(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if grid[0][1] > 1 and grid[1][0] > 1:
return -1
cur = {(0, 0)}
t = 0
while True:
if (m - 1, n - 1) in cur:
return t
nxt = set()
for r, c in cur:
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] <= t + 1:
nxt.add((nr, nc))
cur = nxt
t += 1class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int dr[4] = { 1, -1, 0, 0 }, dc[4] = { 0, 0, 1, -1 };
vector<vector<char>> cur(m, vector<char>(n, 0));
cur[0][0] = 1;
for (int t = 0; ; t++) {
if (cur[m - 1][n - 1]) return t;
vector<vector<char>> next(m, vector<char>(n, 0));
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (!cur[r][c]) continue;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] <= t + 1) next[nr][nc] = 1;
}
}
}
cur = next;
}
}
};function minimumTime(grid) {
const m = grid.length, n = grid[0].length;
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
let cur = Array.from({ length: m }, () => new Array(n).fill(false));
cur[0][0] = true;
for (let t = 0; ; t++) {
if (cur[m - 1][n - 1]) return t;
const next = Array.from({ length: m }, () => new Array(n).fill(false));
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (!cur[r][c]) continue;
for (let k = 0; k < 4; k++) {
const nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] <= t + 1) next[nr][nc] = true;
}
}
}
cur = next;
}
}2Optimal (Dijkstra with parity-aware waiting)
O(m · n · log(m · n))Each cell is settled once and pushes at most four heap entries.O(m · n)The distance grid and the heap.Once the first move is possible, waiting is always available by stepping back and forth, but only in steps of two seconds. So the earliest arrival at a neighbour from time t is t + 1 if it is already open, otherwise its opening time g when g - (t + 1) is even, or g + 1 when it is odd. Arrival times only grow along a path, so Dijkstra with a min-heap on time finds the earliest arrival at every cell.
- If
grid[0][1] > 1andgrid[1][0] > 1, return -1. dist[0][0] = 0; push(0, 0, 0)onto a min-heap ordered by time.- Pop
(t, r, c); skip if stale; returntat the target. - For each neighbour:
nt = t + 1; ifnt < g,nt = g + (g - nt) % 2. Relaxdistand push.
class Solution {
public int minimumTime(int[][] grid) {
int m = grid.length, n = grid[0].length;
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[] { 0, 0, 0 });
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], r = cur[1], c = cur[2];
if (t > dist[r][c]) continue;
if (r == m - 1 && c == n - 1) return t;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int nt = t + 1;
if (nt < grid[nr][nc]) nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.offer(new int[] { nt, nr, nc });
}
}
}
return -1;
}
}class Solution:
def minimumTime(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if grid[0][1] > 1 and grid[1][0] > 1:
return -1
dist = [[float('inf')] * n for _ in range(m)]
dist[0][0] = 0
pq = [(0, 0, 0)]
while pq:
t, r, c = heapq.heappop(pq)
if t > dist[r][c]:
continue
if r == m - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n:
nt = t + 1
if nt < grid[nr][nc]:
nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2
if nt < dist[nr][nc]:
dist[nr][nc] = nt
heapq.heappush(pq, (nt, nr, nc))
return -1class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int dr[4] = { 1, -1, 0, 0 }, dc[4] = { 0, 0, 1, -1 };
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
dist[0][0] = 0;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto [t, r, c] = pq.top();
pq.pop();
if (t > dist[r][c]) continue;
if (r == m - 1 && c == n - 1) return t;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int nt = t + 1;
if (nt < grid[nr][nc]) nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push({nt, nr, nc});
}
}
}
return -1;
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function minimumTime(grid) {
const m = grid.length, n = grid[0].length;
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
const dist = Array.from({ length: m }, () => new Array(n).fill(Infinity));
dist[0][0] = 0;
const pq = new MinHeap((a, b) => a[0] - b[0]);
pq.push([0, 0, 0]);
while (!pq.isEmpty()) {
const [t, r, c] = pq.pop();
if (t > dist[r][c]) continue;
if (r === m - 1 && c === n - 1) return t;
for (let k = 0; k < 4; k++) {
const nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
let nt = t + 1;
if (nt < grid[nr][nc]) nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push([nt, nr, nc]);
}
}
}
return -1;
}Edge cases to test
- Both neighbours of the start open later than time 1 (answer -1)
- Waiting needed where the gap to the opening time is odd vs even (parity)
- A 2 × 2 grid
- All cells already open (answer is m + n - 2)
Hints
Hint 1
You can never stand still, but as soon as you have made one move you can bounce between two cells to burn time two seconds at a time.
Hint 2
So the only impossible case is when you cannot make the very first move. Otherwise every cell is reachable.
Hint 3
Run Dijkstra on arrival times. To enter a neighbour at time t + 1 that opens at g > t + 1, you arrive at g if g - (t + 1) is even, and at g + 1 if it is odd.
FAQ
What is the best time complexity for Minimum Time to Visit a Cell In a Grid?
Optimal (Dijkstra with parity-aware waiting) runs in O(m · n · log(m · n)) time and O(m · n) extra space. Each cell is settled once and pushes at most four heap entries.
Which pattern does Minimum Time to Visit a Cell In a Grid use?
It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time, Find the City With the Smallest Number of Neighbors at a Threshold Distance, Cheapest Flights Within K Stops.
Is there a brute force solution for Minimum Time to Visit a Cell In a Grid?
Yes. Simulate second by second takes O(T · m · n) time and O(m · n) space. Keep the set of cells you could be standing on at time t.
Which edge cases should I test for Minimum Time to Visit a Cell In a Grid?
Both neighbours of the start open later than time 1 (answer -1); Waiting needed where the gap to the opening time is odd vs even (parity); A 2 × 2 grid; All cells already open (answer is m + n - 2).