✅ Dijkstra's Algorithm | Easy to Understand | Detailed Video Explanation 🔥
Intuition\nThe problem requires finding the minimum time to traverse from the top-left to the bottom-right of a grid while adhering to specific constraints on c
# Intuition\nThe problem requires finding the minimum time to traverse from the top-left to the bottom-right of a grid while adhering to specific constraints on cell accessibility. Since the grid has a time constraint for visiting each cell, the goal is to explore paths efficiently and prioritize reaching cells sooner. This suggests using a shortest-path algorithm like Dijkstra\'s, which ensures that we always explore the least-time-consuming paths first.\n\n# Approach\n1. **Initialization**:\n   - Start from the top-left cell at time 0.\n   - Use a priority queue (min-heap) to prioritize cells based on the time required to reach them.\n\n2. **Traversal**:\n   - Use a Dijkstra-like approach, where at each step, the cell with the smallest time value is processed.\n   - For each cell, attempt to move to its neighbors (up, down, left, right).\n   - For each neighbor, calculate the earliest possible time it can be visited. If the difference between the current time and the cell\'s minimum required time is odd, adjust the time to satisfy the constraints.\n\n3. **Conditions**:\n   - If the neighbor cell is out of bounds or already visited, skip it.\n   - If the bottom-right cell is reached, return the time taken.\n\n4. **Termination**:\n   - If the queue is empty and the bottom-right cell has not been reached, return -1.\n\n# Complexity\n- **Time complexity**:  \n  $$O(m \\cdot n \\cdot \\log(m \\cdot n))$$  \n  - The grid has \\(m \\cdot n\\) cells.  \n  - Each cell is processed once, and adding/removing from the priority queue takes \\(O(\\log(m \\cdot n))\\).  \n\n- **Space complexity**:  \n  $$O(m \\cdot n)$$  \n  - Space is required for the `visited` array and the priority queue, both of size \\(m \\cdot n\\).\n\n# Code\n```java []\nclass Solution {\n    // Direction vectors for moving in four directions: right, left, down, up\n    int[][] dir = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };\n    int m, n;\n    boolean[][] visited;\n\n    public int minimumTime(int[][] grid) {\n        // Base case: If both adjacent cells from the start are inaccessible, return -1\n        if (grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n\n        // Initialize dimensions of the grid\n        m = grid.length;\n        n = grid[0].length;\n\n        // Priority queue to implement Dijkstra\'s algorithm (min-heap based on time)\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);\n        visited = new boolean[m][n];\n\n        // Add the starting cell to the priority queue: {row, col, time}\n        pq.offer(new int[]{0, 0, 0});\n\n        // Process the priority queue until empty\n        while (!pq.isEmpty()) {\n            int[] curr = pq.poll();\n            int row = curr[0], col = curr[1], time = curr[2];\n\n            // If the bottom-right cell is reached, return the time taken\n            if (row == m - 1 && col == n - 1) return time;\n\n            // Skip if the current cell is already visited\n            if (visited[row][col]) continue;\n\n            // Mark the current cell as visited\n            visited[row][col] = true;\n\n            // Explore all four possible directions\n            for (int[] d : dir) {\n                int r = row + d[0], c = col + d[1];\n\n                // Check if the neighboring cell is valid (within bounds and not visited)\n                if (!valid(r, c)) continue;\n\n                // Calculate the earliest time to reach the neighboring cell\n                // Adjust time based on parity to match the cell\'s constraint\n                int f = (grid[r][c] - time) % 2 == 0 ? 1 : 0;\n                int t = Math.max(time + 1, grid[r][c] + f);\n\n                // Add the neighboring cell to the priority queue\n                pq.offer(new int[]{r, c, t});\n            }\n        }\n        // If the bottom-right cell is unreachable, return -1\n        return -1;\n    }\n\n    // Helper method to check if a cell is within bounds and not visited\n    private boolean valid(int i, int j) {\n        return i >= 0 && j >= 0 && i < m && j < n && !visited[i][j];\n    }\n}\n```\n\n\nLeetCode 2577 Minimum Time to Visit a Cell In a Grid | Graph | Hard | Dijkstra\'s algo | Google\nhttps://youtu.be/u72HaTxPg0Q
['Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'Java']