Minimum Time to a visit a cell in a grid

XXX. Minimum Time to Visit a Cell In a Grid

Graph

Dijkstra's Algorithm

Shortest Path

Problem Statement:

Given a 2D grid where each cell contains a non-negative integer representing the earliest time you can visit that cell, find the minimum time required to travel from the top-left corner to the bottom-right corner. You can only move up, down, left, or right at each step.

Algorithm:

The solution uses a variation of Dijkstra's algorithm to find the shortest path:

1. Use a priority queue to keep track of cells to visit, sorted by the time required to reach them.
2. Start from the top-left corner with an initial time of 0.
3. At each step, pop the cell with the smallest time from the priority queue.
   • If this cell is the bottom-right corner, return the time.
   • Otherwise, visit its neighbors and calculate the earliest time you can reach them, considering the time constraint of the grid.
4. Continue until the queue is empty or the destination is reached.

Complexity:

Time Complexity: O(m * n * log(m * n)), where m and n are the grid dimensions. The priority queue ensures logarithmic time for insertions and deletions.
Space Complexity: O(m * n), for the visited set and priority queue.

Java Implementation:

import java.util.*;

public class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        PriorityQueue pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        boolean[][] visited = new boolean[m][n];

        pq.offer(new int[]{0, 0, 0}); // {row, col, time}

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int row = current[0], col = current[1], time = current[2];

            if (row == m - 1 && col == n - 1) return time;

            if (visited[row][col]) continue;
            visited[row][col] = true;

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    int waitTime = Math.max(0, grid[newRow][newCol] - (time + 1));
                    pq.offer(new int[]{newRow, newCol, time + 1 + waitTime});
                }
            }
        }

        return -1; // If destination is not reachable
    }
}