2577. Minimum Time to Visit a Cell In a Grid LeetCode Solution

In this guide, you will get 2577. Minimum Time to Visit a Cell In a Grid LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Visit a Cell 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.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Time to Visit a Cell In a Grid solution in C++
  4. Minimum Time to Visit a Cell In a Grid solution in Java
  5. Minimum Time to Visit a Cell In a Grid solution in Python
  6. Additional Resources
2577. Minimum Time to Visit a Cell In a Grid LeetCode Solution image

Problem Statement of Minimum Time to Visit a Cell In a Grid

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].
You are standing in the top-left cell of the matrix in the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.
Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

Example 1:

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7
Explanation: One of the paths that we can take is the following:
– at t = 0, we are on the cell (0,0).
– at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
– at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
– at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
– at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
– at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
– at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
– at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.

See also  2706. Buy Two Chocolates LeetCode Solution

Example 2:

Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
Output: -1
Explanation: There is no path from the top left to the bottom-right cell.

Constraints:

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
0 <= grid[i][j] <= 105
grid[0][0] == 0

Complexity Analysis

  • Time Complexity: O(mn\log mn)
  • Space Complexity: O(mn)

2577. Minimum Time to Visit a Cell In a Grid LeetCode Solution in C++

class Solution {
 public:
  int minimumTime(vector<vector<int>>& grid) {
    if (grid[0][1] > 1 && grid[1][0] > 1)
      return -1;

    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = grid.size();
    const int n = grid[0].size();
    using T = tuple<int, int, int>;  // (time, i, j)
    priority_queue<T, vector<T>, greater<>> minHeap;
    vector<vector<bool>> seen(m, vector<bool>(n));

    minHeap.emplace(0, 0, 0);
    seen[0][0] = true;

    while (!minHeap.empty()) {
      const auto [time, i, j] = minHeap.top();
      minHeap.pop();
      if (i == m - 1 && j == n - 1)
        return time;
      for (const auto& [dx, dy] : dirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        const int extraWait = (grid[x][y] - time) % 2 == 0 ? 1 : 0;
        const int nextTime = max(time + 1, grid[x][y] + extraWait);
        minHeap.emplace(nextTime, x, y);
        seen[x][y] = true;
      }
    }

    throw;
  }
};
/* code provided by PROGIEZ */

2577. Minimum Time to Visit a Cell In a Grid LeetCode Solution in Java

class Solution {
  public int minimumTime(int[][] grid) {
    if (grid[0][1] > 1 && grid[1][0] > 1)
      return -1;

    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = grid.length;
    final int n = grid[0].length;
    Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])) {
      { offer(new int[] {0, 0, 0}); } // (time, i, j)
    };
    boolean[][] seen = new boolean[m][n];
    seen[0][0] = true;

    while (!minHeap.isEmpty()) {
      final int time = minHeap.peek()[0];
      final int i = minHeap.peek()[1];
      final int j = minHeap.poll()[2];
      if (i == m - 1 && j == n - 1)
        return time;
      for (int[] dir : dirs) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        final int extraWait = (grid[x][y] - time) % 2 == 0 ? 1 : 0;
        final int nextTime = Math.max(time + 1, grid[x][y] + extraWait);
        minHeap.offer(new int[] {nextTime, x, y});
        seen[x][y] = true;
      }
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

2577. Minimum Time to Visit a Cell In a Grid LeetCode Solution in Python

class Solution:
  def minimumTime(self, grid: list[list[int]]) -> int:
    if grid[0][1] > 1 and grid[1][0] > 1:
      return -1

    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(grid)
    n = len(grid[0])
    minHeap = [(0, 0, 0)]  # (time, i, j)
    seen = {(0, 0)}

    while minHeap:
      time, i, j = heapq.heappop(minHeap)
      if i == m - 1 and j == n - 1:
        return time
      for dx, dy in dirs:
        x = i + dx
        y = j + dy
        if x < 0 or x == m or y < 0 or y == n:
          continue
        if (x, y) in seen:
          continue
        extraWait = 1 if (grid[x][y] - time) % 2 == 0 else 0
        nextTime = max(time + 1, grid[x][y] + extraWait)
        heapq.heappush(minHeap, (nextTime, x, y))
        seen.add((x, y))
# code by PROGIEZ

Additional Resources

See also  3453. Separate Squares I LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.