Minimum Number of Visited Cells in a Grid

Hard
1709.

Minimum Number of Visited Cells in a Grid

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.

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) with j < k <= grid[i][j] + j, or
  • down to any cell (k, j) with i < 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.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] < m * n
  • grid[m - 1][n - 1] == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumVisitedCells = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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) with j < k <= grid[i][j] + j, or
  • down to any cell (k, j) with i < 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.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] < m * n
  • grid[m - 1][n - 1] == 0

Hints for Minimum Number of Visited Cells in a Grid

  1. 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).

  2. Hint 2

    A cell can jump to up to m + n others, so scanning every target from every cell is O(mn(m + n)). But once a cell has been discovered, it never needs to be scanned again.

  3. 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

  1. Row pointers R[i][j] (with sentinel j = n) and column pointers C[j][i] (sentinel i = m) start pointing at themselves; removing a cell makes it point to the next index.
  2. Remove (0, 0) from both structures; queue it with distance 1.
  3. Pop (i, j) with distance d. Scan right: k = findRow(i, j + 1) while k <= min(n - 1, j + grid[i][j]) — record d + 1, queue it, remove it from its row and column, continue from findRow(i, k + 1).
  4. Scan down the same way with the column structure.
  5. 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 1 grid 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