LeetCode Solutions Blog

Minimum Number of Visited Cells in a Grid

Number: 2697

Difficulty: Hard

Paid? No

Problem Description

Given an m x n grid where each cell grid[i][j] indicates the maximum number of steps you can move either rightward or downward from that cell, determine the minimum number of cells you need to visit to reach the bottom-right cell. If no valid path exists, return -1.

Key Insights

Model the grid as a graph with nodes representing cells and edges representing valid moves.
Use Breadth-First Search (BFS) to find the shortest path in an unweighted graph.
To avoid TLE when many cells can be reached from each node, maintain pointers (or indices) that record how far you have already processed in each row and column. This prevents re‐exploration of previously scanned segments.
Mark cells as visited to prevent redundant work.

Space and Time Complexity

Time Complexity: O(m * n) – Each cell is processed at most once using the controlled range scanning. Space Complexity: O(m * n) – For the BFS queue and auxiliary arrays for visited nodes.

Solution

We use a BFS approach starting from cell (0,0). For each cell (i, j) the grid value provides two ranges:

Rightward moves: from column j+1 to min(n-1, j + grid[i][j])
Downward moves: from row i+1 to min(m-1, i + grid[i][j]) To avoid checking the same segments repeatedly, we maintain two arrays:

next_in_row[i]: the next unprocessed column in row i.
next_in_col[j]: the next unprocessed row in column j. At each step, we update these pointers after processing the respective range and add newly reachable, unvisited cells to the BFS queue. The path length is tracked as the number of cells visited so far; when we reach the bottom-right, we return that count.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution using BFS with range control in rows and columns
from collections import deque

def minVisitedCells(grid):
    m, n = len(grid), len(grid[0])
    # Initialize visited matrix
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    # BFS queue stores tuples of (row, col, steps)
    queue = deque([(0, 0, 1)])
    # Arrays to store the next unprocessed index per row and per column
    next_in_row = [0] * m
    next_in_col = [0] * n

    while queue:
        i, j, steps = queue.popleft()
        # If reached bottom-right, return number of steps (cells visited)
        if i == m - 1 and j == n - 1:
            return steps

        # Process rightward moves in row i:
        # Determine starting column (avoid reprocessing earlier columns)
        start_col = max(j + 1, next_in_row[i])
        # End of range (non-inclusive)
        end_col = min(n, j + grid[i][j] + 1)
        for nj in range(start_col, end_col):
            if not visited[i][nj]:
                visited[i][nj] = True
                queue.append((i, nj, steps + 1))
        # Update next_in_row pointer to avoid reprocessing the same columns
        next_in_row[i] = max(next_in_row[i], j + grid[i][j] + 1)

        # Process downward moves in column j:
        start_row = max(i + 1, next_in_col[j])
        end_row = min(m, i + grid[i][j] + 1)
        for ni in range(start_row, end_row):
            if not visited[ni][j]:
                visited[ni][j] = True
                queue.append((ni, j, steps + 1))
        # Update next_in_col pointer for column j
        next_in_col[j] = max(next_in_col[j], i + grid[i][j] + 1)

    return -1

# Example usage:
# grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
# print(minVisitedCells(grid))