2617. Minimum Number of Visited Cells in a Grid

Description

You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0).

Starting from the cell (i, j), you can move to one of the following cells:

• Cells (i, k) with j < k <= grid[i][j] + j (rightward movement), or
• Cells (k, j) with i < k <= grid[i][j] + i (downward movement).

Return the minimum number of cells you need to visit to reach the bottom-right cell (m - 1, n - 1). If there is no valid path, 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: The image above shows one of the paths that visits exactly 4 cells.

Example 2:

Input: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
Output: 3
Explanation: The image above shows one of the paths that visits exactly 3 cells.

Example 3:

Input: grid = [[2,1,0],[1,0,0]]
Output: -1
Explanation: It can be proven that no path exists.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 0 <= grid[i][j] < m * n
• grid[m - 1][n - 1] == 0

 

Solutions

Solution: Segment Tree

• Time complexity: O(mn(log(m + n)))
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
const minimumVisitedCells = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const rows = Array.from({ length: m }, () => new SegmentTree(n));
  const cols = Array.from({ length: n }, () => new SegmentTree(m));

  rows[m - 1].update(n - 1, 1);
  cols[n - 1].update(m - 1, 1);

  for (let row = m - 1; row >= 0; row--) {
    for (let col = n - 1; col >= 0; col--) {
      const value = grid[row][col];

      if (!value) continue;

      const colK = Math.min(col + value, n - 1);
      const rowK = Math.min(row + value, m - 1);
      const moveRight = rows[row].query(col + 1, colK);
      const moveDown = cols[col].query(row + 1, rowK);
      const minMove = Math.min(moveRight, moveDown);

      if (minMove !== Number.MAX_SAFE_INTEGER) {
        const steps = minMove + 1;

        rows[row].update(col, steps);
        cols[col].update(row, steps);
      }
    }
  }

  const result = rows[0].query(0, 0);

  return result === Number.MAX_SAFE_INTEGER ? -1 : result;
};

class SegmentTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(n * 4).fill(Number.MAX_SAFE_INTEGER);
  }

  update(index, val) {
    this.#update(0, 0, this.n - 1, index, val);
  }

  query(low, high) {
    return this.#query(0, 0, this.n - 1, low, high);
  }

  merge(index) {
    return Math.min(this.tree[index * 2 + 1], this.tree[index * 2 + 2]);
  }

  #update(index, left, right, target, val) {
    if (left === right) {
      this.tree[index] = val;
      return;
    }

    const mid = Math.floor((left + right) / 2);

    if (target <= mid) {
      this.#update(index * 2 + 1, left, mid, target, val);
    } else {
      this.#update(index * 2 + 2, mid + 1, right, target, val);
    }

    this.tree[index] = this.merge(index);
  }

  #query(index, left, right, low, high) {
    if (low <= left && high >= right) {
      return this.tree[index];
    }

    if (low > right || high < left) {
      return Number.MAX_SAFE_INTEGER;
    }

    const mid = Math.floor((left + right) / 2);
    const leftValue = this.#query(index * 2 + 1, left, mid, low, high);
    const rightValue = this.#query(index * 2 + 2, mid + 1, right, low, high);

    return Math.min(leftValue, rightValue);
  }
}