2617. Minimum Number of Visited Cells in a Grid LeetCode Solution
In this guide, you will get 2617. Minimum Number of Visited Cells in a Grid LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Visited Cells in a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Visited Cells in a Grid
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.
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
Complexity Analysis
Time Complexity: O(mn(\log n + \log m))
Space Complexity: O(mn)
2617. Minimum Number of Visited Cells in a Grid LeetCode Solution in C++
class SegmentTree {
public:
explicit SegmentTree(int n, int kInf) : kInf(kInf), n(n), tree(4 * n, kInf) {}
// Updates nums[i] to val.
void update(int i, int val) {
update(0, 0, n - 1, i, val);
}
// Returns min(nums[i..j]).
int query(int i, int j) const {
return query(0, 0, n - 1, i, j);
}
private:
const int kInf; // the invalid value
const int n; // the size of the input array
vector<int> tree; // the segment tree
void update(int treeIndex, int lo, int hi, int i, int val) {
if (lo == hi) {
tree[treeIndex] = val;
return;
}
const int mid = (lo + hi) / 2;
if (i <= mid)
update(2 * treeIndex + 1, lo, mid, i, val);
else
update(2 * treeIndex + 2, mid + 1, hi, i, val);
tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
int query(int treeIndex, int lo, int hi, int i, int j) const {
if (i <= lo && hi <= j) // [lo, hi] lies completely inside [i, j].
return tree[treeIndex];
if (j < lo || hi < i) // [lo, hi] lies completely outside [i, j].
return kInf;
const int mid = (lo + hi) / 2;
return merge(query(treeIndex * 2 + 1, lo, mid, i, j),
query(treeIndex * 2 + 2, mid + 1, hi, i, j));
}
int merge(int left, int right) const {
return min(left, right);
}
};
class Solution {
public:
int minimumVisitedCells(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
const int kInf = (m + n) * 2 - 1;
vector<SegmentTree> rows(m, SegmentTree(n, kInf));
vector<SegmentTree> cols(n, SegmentTree(m, kInf));
// The min # cells to visit (m - 1, n - 1) from (m - 1, n - 1) is 1.
rows[m - 1].update(n - 1, 1);
cols[n - 1].update(m - 1, 1);
for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j) {
// There's no k s.t. j < k <= 0 + j.
// There's no k s.t. i < k <= 0 + i.
if (grid[i][j] == 0)
continue;
const int moveRight = rows[i].query(j + 1, grid[i][j] + j);
const int moveDown = cols[j].query(i + 1, grid[i][j] + i);
const int minMove = min(kInf, min(moveRight, moveDown) + 1);
rows[i].update(j, minMove);
cols[j].update(i, minMove);
}
const int res = rows[0].query(0, 0);
return res == kInf ? -1 : res;
}
}; /* code provided by PROGIEZ */
2617. Minimum Number of Visited Cells in a Grid LeetCode Solution in Java
N/A // code provided by PROGIEZ
2617. Minimum Number of Visited Cells in a Grid LeetCode Solution in Python
