Java Solution for Minimum Time to Visit a Cell In a Grid Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be visualized as navigating through a grid where each cell represents a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be visualized as navigating through a grid where each cell represents a \u201Cgate\u201D that opens only at or after a specific time (grid[row][col]). The goal is to reach the bottom-right corner (m-1, n-1) from the top-left (0, 0) in the minimum possible time. Each move (up, down, left, right) takes exactly 1 second, but sometimes you must \u201Cwait\u201D for the gate (cell) to open. The task is similar to finding the shortest path in a weighted graph, where the weight is dynamic based on time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tDijkstra-like Algorithm:\n\t\u2022\tUse a priority queue (min-heap) to explore the grid in order of the earliest possible time to reach each cell.\n\t\u2022\tEach entry in the queue is a triplet {row, col, time}, representing the cell and the time it took to reach it.\n2.\tInitialization:\n\t\u2022\tStart from (0, 0) at time 0 and push this into the priority queue.\n\t\u2022\tIf the only adjacent cells (0, 1) or (1, 0) require a time greater than 1, return -1 immediately since you can\u2019t move.\n3.\tTime Calculation for Moves:\n\t\u2022\tFor each move to a neighboring cell (newRow, newCol), the time increases by 1.\n\t\u2022\tIf the nextTime (current time + 1) is less than the cell\u2019s required time (grid[newRow][newCol]), calculate how much longer you must wait:\n\t\u2022\tIf the difference is even, move at grid[newRow][newCol].\n\t\u2022\tIf the difference is odd, wait an extra second to synchronize and move at grid[newRow][newCol] + 1.\n4.\tVisited Array:\n\t\u2022\tTrack visited cells using a boolean[][] visited array to avoid redundant processing.\n5.\tTermination:\n\t\u2022\tIf you reach the bottom-right cell (m-1, n-1), return the current time.\n\t\u2022\tIf the queue is empty and the bottom-right has not been reached, return -1\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime Complexity: O(m x n log(m x n))\n\n\u2022\tThe grid contains m x n cells.\n\u2022\tEach cell can be added to the priority queue at most once, so there are O(m x n) insertions.\n\u2022\tEach insertion and extraction from the priority queue takes O(log(m x n)).\n\u2022\tThus, the total complexity is O(m x n log(m x n)).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace Complexity: O(m x n)\n\n\u2022\tPriority Queue: Stores up to O(m x n) cells at any time.\n\u2022\tVisited Array: An array of size m x n to track visited cells.\n\u2022\tAuxiliary Data: Small constant space for temporary variables and directions array.\n\n# Code\n```java []\nclass Solution {\n    public int minimumTime(int[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n\n        if (grid[0][1] > 1 && grid[1][0] > 1) {\n            return -1;\n        }\n\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));\n        pq.offer(new int[]{0, 0, 0});  \n\n        boolean[][] visited = new boolean[m][n];\n        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n\n        while (!pq.isEmpty()) {\n            int[] current = pq.poll();\n            int row = current[0], col = current[1], time = current[2];\n\n            if (row == m - 1 && col == n - 1) {\n                return time;\n            }\n\n            if (visited[row][col]) continue;\n            visited[row][col] = true;\n\n            for (int[] dir : directions) {\n                int newRow = row + dir[0];\n                int newCol = col + dir[1];\n\n                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {\n                    int nextTime = time + 1;\n                    int requiredTime = grid[newRow][newCol];\n\n                    \n                    if (nextTime < requiredTime) {\n                        int wait = (requiredTime - nextTime) % 2 == 0 ? 0 : 1;\n                        nextTime = requiredTime + wait;\n                    }\n\n                    if (!visited[newRow][newCol]) {\n                        pq.offer(new int[]{newRow, newCol, nextTime});\n                    }\n                }\n            }\n        }\n\n        return -1;\n    }\n}\n```
['Java']