LeetCode 2617 - Minimum Number of Visited Cells in a Grid

LeetCode Problem 2617

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Stack, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix, Monotonic Stack

Solution

Problem Understanding

The problem asks us to determine the minimum number of cells we need to visit in order to reach the bottom-right corner of a given m x n grid. Each cell (i, j) contains a number grid[i][j] representing the maximum number of steps we can move right or down from that cell. Specifically, from (i, j) we can move to any cell (i, k) where j < k <= j + grid[i][j] or any cell (k, j) where i < k <= i + grid[i][j]. The goal is to find the shortest path in terms of the number of visited cells, not the number of steps or distances. If reaching the bottom-right is impossible, we return -1.

The input guarantees that 1 <= m, n <= 10^5 and 1 <= m * n <= 10^5, meaning although a single dimension can be very large, the total number of cells is bounded to 10^5. This ensures we can process the grid as a flat structure if needed. The value in each cell is less than m * n and the bottom-right cell is always 0, meaning we cannot move from that cell.

Important edge cases include grids with only one row or one column, cells with 0 that block further movement, and grids where the path is blocked early.

Approaches

The brute-force approach would be to perform a standard breadth-first search (BFS) from the top-left cell. For each cell (i, j), we would enqueue all possible rightward and downward cells reachable according to grid[i][j]. This guarantees correctness because BFS finds the shortest path in an unweighted graph. However, it is too slow because each cell could potentially enqueue up to O(m + n) cells, leading to a total time complexity of O((m * n) * (m + n)). For the constraints (m * n <= 10^5), this is not feasible.

The key insight for the optimal solution is that we do not need to enqueue every individual reachable cell. We can keep track of the farthest reachable cells in each row and column. Using BFS, we only need to move to new farthest points in each direction. By maintaining two arrays maxRight[i] and maxDown[j] representing the farthest unvisited cell in row i and column j, we avoid revisiting cells unnecessarily and reduce redundant operations.

Algorithm Walkthrough

1. Initialize a queue for BFS and start from (0, 0) with distance 1 because visiting the first cell counts.
2. Maintain two arrays: maxRight[i] for the farthest column reached in row i, and maxDown[j] for the farthest row reached in column j.
3. While the queue is not empty, dequeue the current cell (r, c) and its current distance d.
4. For rightward movement, calculate the farthest column reachable: endCol = min(n - 1, c + grid[r][c]). Iterate from maxRight[r] + 1 to endCol, enqueue each cell (r, newCol) with distance d + 1, and update maxRight[r] to endCol.
5. For downward movement, calculate the farthest row reachable: endRow = min(m - 1, r + grid[r][c]). Iterate from maxDown[c] + 1 to endRow, enqueue each cell (newRow, c) with distance d + 1, and update maxDown[c] to endRow.
6. If we reach (m - 1, n - 1), return the current distance.
7. If the queue empties without reaching the target, return -1.

Why it works: The BFS guarantees that the first time we reach a cell is through the minimum number of visited cells because BFS explores all cells layer by layer. Tracking maxRight and maxDown ensures we never enqueue the same cell twice, maintaining correctness while improving efficiency.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if m == 1 and n == 1:
            return 1

        maxRight = [-1] * m
        maxDown = [-1] * n
        queue = deque([(0, 0, 1)])  # (row, col, distance)

        while queue:
            r, c, dist = queue.popleft()

            # Move right
            endCol = min(n - 1, c + grid[r][c])
            for newC in range(maxRight[r] + 1, endCol + 1):
                if newC == n - 1 and r == m - 1:
                    return dist + 1
                queue.append((r, newC, dist + 1))
            maxRight[r] = max(maxRight[r], endCol)

            # Move down
            endRow = min(m - 1, r + grid[r][c])
            for newR in range(maxDown[c] + 1, endRow + 1):
                if newR == m - 1 and c == n - 1:
                    return dist + 1
                queue.append((newR, c, dist + 1))
            maxDown[c] = max(maxDown[c], endRow)

        return -1

The implementation starts BFS from (0, 0) and tracks the farthest reached indices in each row and column. The for loops only enqueue cells that have not been visited yet, ensuring that each cell is processed at most once. The check for (m - 1, n - 1) allows an early return.

Go Solution

package main

import "container/list"

func minimumVisitedCells(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    if m == 1 && n == 1 {
        return 1
    }

    maxRight := make([]int, m)
    maxDown := make([]int, n)
    for i := 0; i < m; i++ { maxRight[i] = -1 }
    for j := 0; j < n; j++ { maxDown[j] = -1 }

    type Cell struct {
        r, c, dist int
    }

    queue := list.New()
    queue.PushBack(Cell{0, 0, 1})

    for queue.Len() > 0 {
        front := queue.Remove(queue.Front()).(Cell)
        r, c, dist := front.r, front.c, front.dist

        // Move right
        endCol := c + grid[r][c]
        if endCol >= n {
            endCol = n - 1
        }
        for newC := maxRight[r] + 1; newC <= endCol; newC++ {
            if newC == n-1 && r == m-1 {
                return dist + 1
            }
            queue.PushBack(Cell{r, newC, dist + 1})
        }
        if endCol > maxRight[r] {
            maxRight[r] = endCol
        }

        // Move down
        endRow := r + grid[r][c]
        if endRow >= m {
            endRow = m - 1
        }
        for newR := maxDown[c] + 1; newR <= endRow; newR++ {
            if newR == m-1 && c == n-1 {
                return dist + 1
            }
            queue.PushBack(Cell{newR, c, dist + 1})
        }
        if endRow > maxDown[c] {
            maxDown[c] = endRow
        }
    }

    return -1
}

In Go, we use container/list to implement BFS. We define a struct Cell to store row, column, and distance. The logic mirrors Python, with attention to Go's zero-initialization and explicit queue management.

Worked Examples

Example 1: grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]

Start from (0,0), grid[0][0] = 3. Right moves: (0,1),(0,2),(0,3). Down moves: (1,0),(2,0),(3,0). BFS will explore layer by layer and reach (3,3) in 4 steps.

Example 2: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]

Optimal path: (0,0) -> (0,1) -> (1,1) -> (3,1) totaling 3