Minimum Number of Visited Cells in a Grid — Solution
Minimum Number of Visited Cells in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Number of Visited Cells in a Grid is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix, Breadth-First Search, Stack, Heap, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n matrix grid of non-negative integers and start in the top-left cell (0, 0).
From a cell (i, j) you may jump:
- right to any cell
(i, k)withj < k <= grid[i][j] + j, or - down to any cell
(k, j)withi < k <= grid[i][j] + i.
Return the minimum number of cells you visit on the way to the bottom-right cell (m - 1, n - 1), counting both the starting and the final cell. If it cannot be reached, return -1.
Example 1
Input: grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
Output: 4
Explanation: One shortest route is (0,0) → (0,1) → (3,1) → (3,3): four cells.
Example 2
Input: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
Output: 3
Explanation: (0,0) → (3,0) → (3,3).
Example 3
Input: grid = [[2,1,0],[1,0,0]]
Output: -1
Explanation: Every route stalls on a 0 before the corner.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 10^51 <= m * n <= 10^50 <= grid[i][j] < m * ngrid[m - 1][n - 1] == 0
Hints for Minimum Number of Visited Cells in a Grid
Hint 1
Each jump costs one more visited cell regardless of its length, so this is a shortest path in an unweighted graph: BFS from
(0, 0).Hint 2
A cell can jump to up to
m + nothers, so scanning every target from every cell isO(mn(m + n)). But once a cell has been discovered, it never needs to be scanned again.Hint 3
Keep, for every row and every column, a 'next unvisited cell' pointer structure (union-find with path compression, or a sorted set). A BFS step then walks only over cells that are still unvisited and removes them as it goes.
How to solve Minimum Number of Visited Cells in a Grid
BFS gives the minimum number of jumps, but the naive neighbour scan revisits the same already-seen cells over and over. Each row and each column keeps a 'next unvisited' pointer: when a cell is discovered it is removed from both its row and its column, and the scan from any later cell jumps straight past it. Every cell is removed once, so the BFS is near-linear.
Approach
- Row pointers
R[i][j](with sentinelj = n) and column pointersC[j][i](sentineli = m) start pointing at themselves; removing a cell makes it point to the next index. - Remove
(0, 0)from both structures; queue it with distance 1. - Pop
(i, j)with distanced. Scan right:k = findRow(i, j + 1)whilek <= min(n - 1, j + grid[i][j])— recordd + 1, queue it, remove it from its row and column, continue fromfindRow(i, k + 1). - Scan down the same way with the column structure.
- Return the distance recorded for
(m - 1, n - 1), or-1.
Why it works
BFS order guarantees the first time a cell is discovered is with the fewest visited cells. Removing a discovered cell from its row and column cannot lose a shorter route, because any later discovery would only offer a larger distance. Path compression makes every find amortised near-constant, and each cell is removed exactly once.
Complexity
- Time —
O(mn · α(mn)) - Space —
O(mn)
Pitfalls
- Count cells, not jumps: the start itself counts, so a
1 x 1grid answers 1. - A cell must be removed from both its row and its column structure when discovered, whichever direction found it.
- Clip each scan at the grid edge as well as at
grid[i][j].
Reference solution
Python
from typing import List
from collections import deque
def minimumVisitedCells(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
row = [list(range(n + 1)) for _ in range(m)]
col = [list(range(m + 1)) for _ in range(n)]
def find(p, x):
root = x
while p[root] != root:
root = p[root]
while p[x] != root:
p[x], x = root, p[x]
return root
dist = [[-1] * n for _ in range(m)]
def visit(i, j, d):
dist[i][j] = d
row[i][j] = j + 1
col[j][i] = i + 1
q.append((i, j))
q = deque()
visit(0, 0, 1)
while q:
i, j = q.popleft()
d, g = dist[i][j], grid[i][j]
k = find(row[i], j + 1)
while k <= min(n - 1, j + g):
visit(i, k, d + 1)
k = find(row[i], k + 1)
k = find(col[j], i + 1)
while k <= min(m - 1, i + g):
visit(k, j, d + 1)
k = find(col[j], k + 1)
return dist[m - 1][n - 1]Java
static int findPtr(int[] p, int base, int x) {
int root = x;
while (p[base + root] != root) root = p[base + root];
while (p[base + x] != root) { int t = p[base + x]; p[base + x] = root; x = t; }
return root;
}
public static int minimumVisitedCells(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] R = new int[m * (n + 1)], C = new int[n * (m + 1)];
for (int i = 0; i < m; i++) for (int j = 0; j <= n; j++) R[i * (n + 1) + j] = j;
for (int j = 0; j < n; j++) for (int i = 0; i <= m; i++) C[j * (m + 1) + i] = i;
int[] dist = new int[m * n];
Arrays.fill(dist, -1);
int[] q = new int[m * n];
int head = 0, tail = 0;
dist[0] = 1; R[0] = 1; C[0] = 1; q[tail++] = 0;
while (head < tail) {
int cell = q[head++], i = cell / n, j = cell % n, d = dist[cell], g = grid[i][j];
int lim = Math.min(n - 1, j + g);
for (int k = findPtr(R, i * (n + 1), j + 1); k <= lim; k = findPtr(R, i * (n + 1), k + 1)) {
dist[i * n + k] = d + 1; R[i * (n + 1) + k] = k + 1; C[k * (m + 1) + i] = i + 1; q[tail++] = i * n + k;
}
int lim2 = Math.min(m - 1, i + g);
for (int k = findPtr(C, j * (m + 1), i + 1); k <= lim2; k = findPtr(C, j * (m + 1), k + 1)) {
dist[k * n + j] = d + 1; R[k * (n + 1) + j] = j + 1; C[j * (m + 1) + k] = k + 1; q[tail++] = k * n + j;
}
}
return dist[m * n - 1];
}C++
int findPtr(vector<int>& p, int base, int x) {
int root = x;
while (p[base + root] != root) root = p[base + root];
while (p[base + x] != root) { int t = p[base + x]; p[base + x] = root; x = t; }
return root;
}
int minimumVisitedCells(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> R(m * (n + 1)), C(n * (m + 1)), dist(m * n, -1), q;
for (int i = 0; i < m; i++) for (int j = 0; j <= n; j++) R[i * (n + 1) + j] = j;
for (int j = 0; j < n; j++) for (int i = 0; i <= m; i++) C[j * (m + 1) + i] = i;
auto visit = [&](int i, int j, int d) {
dist[i * n + j] = d;
R[i * (n + 1) + j] = j + 1;
C[j * (m + 1) + i] = i + 1;
q.push_back(i * n + j);
};
visit(0, 0, 1);
for (size_t h = 0; h < q.size(); h++) {
int i = q[h] / n, j = q[h] % n, d = dist[q[h]], g = grid[i][j];
int lim = min(n - 1, j + g);
for (int k = findPtr(R, i * (n + 1), j + 1); k <= lim; k = findPtr(R, i * (n + 1), k + 1)) visit(i, k, d + 1);
int lim2 = min(m - 1, i + g);
for (int k = findPtr(C, j * (m + 1), i + 1); k <= lim2; k = findPtr(C, j * (m + 1), k + 1)) visit(k, j, d + 1);
}
return dist[m * n - 1];
}JavaScript
var minimumVisitedCells = function(grid) {
var m = grid.length, n = grid[0].length;
// row pointers at i*(n+1)+j, column pointers at j*(m+1)+i
var R = new Array(m * (n + 1)), C = new Array(n * (m + 1));
for (var a = 0; a < m; a++) for (var b = 0; b <= n; b++) R[a * (n + 1) + b] = b;
for (var c = 0; c < n; c++) for (var e = 0; e <= m; e++) C[c * (m + 1) + e] = e;
var find = function(P, base, x) {
var root = x;
while (P[base + root] !== root) root = P[base + root];
while (P[base + x] !== root) { var t = P[base + x]; P[base + x] = root; x = t; }
return root;
};
var dist = new Array(m * n);
for (var z = 0; z < m * n; z++) dist[z] = -1;
var q = [];
var visit = function(i, j, d) {
dist[i * n + j] = d;
R[i * (n + 1) + j] = j + 1;
C[j * (m + 1) + i] = i + 1;
q.push(i * n + j);
};
visit(0, 0, 1);
for (var h = 0; h < q.length; h++) {
var i = Math.floor(q[h] / n), j = q[h] % n, d = dist[q[h]], g = grid[i][j];
var lim = Math.min(n - 1, j + g);
for (var k = find(R, i * (n + 1), j + 1); k <= lim; k = find(R, i * (n + 1), k + 1)) visit(i, k, d + 1);
var lim2 = Math.min(m - 1, i + g);
for (var k2 = find(C, j * (m + 1), i + 1); k2 <= lim2; k2 = find(C, j * (m + 1), k2 + 1)) visit(k2, j, d + 1);
}
return dist[m * n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming