Minimum Time to visit a cell in a grid - Easy Explanation -🌟 Beats 100% 🌟
Intuition\n \nPriority Queue can be used with the custom comparator that the first element of the prioirity Queue array that is time is arranged in ascending or
# Intuition\n \nPriority Queue can be used with the custom comparator that the first element of the prioirity Queue array that is time is arranged in ascending order in the priorityQueue.\n\nTo check if the cell is already visited or not, seen boolean array is used for the size of the grid.\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n**Static variable**:\n\nInitialize static array MOVES , all four directions that are possible from one grid position.\n\n    private static final int[][] MOVES={{-1,0},{0,1},{1,0},{0,-1}};\n\n**Initialization**:\n\nInitialize rows to be the number of rows in the grid(grid.length) and cols to be the number of column in the grid(grid[0].length).\n\n    int rows=grid.length;\n    int cols=grid[0].length;\n\n**Base Condition**:\n\nIf the element in the next time of the grid may in 0,1 or 1,0 cell -> if both are greater than time 1, We cannot move further , then we return -1.\n\n    if(grid[0][1]>1 && grid[1][0]>1)\n    {\n        return -1;\n    }\n\n**Initialization for processing of the grid**:\n\nDeclare priority Queue with the element as integer array and with custom comparator as a[0] < b[0] in the ascending order of time.\n\n    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);\n\nDeclare boolean array seen with the size of the grid.\n\n    boolean[][] seen=new boolean[rows][cols];\n\nInitialize priorityQueue with first element as {0,0,0} because at the grid position (0,0) -> the time is also 0.\n\n    pq.offer(new int[]{0,0,0});\n\nInitialize the first position (0,0) to be true because it is now reached and it could not be visited again.\n\n    seen[0][0]=true;\n\n**Finding Minimum Time to visit**:\n\nIterate through the priority Queue until it is empty.\n\n    while(!pq.isEmpty()){\n\nFrom the priorityQueue , poll the element which is the integer array with time(curr[0]) , row(curr[1]) and col(curr[2]).\n\n    int[] curr=pq.poll();\n    int time=curr[0];\n    int row=curr[1];\n    int col=curr[2];\n\nIterate through all the direction that is possible.\n\n    \n        for(int[] dir:MOVES){\n\nFind newRow(row+dir[0]) and column(col+dir[1]) by adding with the original row and column and check if it is within 0 to number of rows or cols.Otherwise , continue with next iteration.\n\n    int newRow=row+dir[0];\n    int newCol=col+dir[1];\n\n    if(newRow<0 || newRow>=rows || newCol<0 || newCol>=cols || seen[newRow][newCol])\n    {\n        continue;\n    }\n\nAnd newTime is equal to the available time plus 1.\n\n    int newTime=time+1;\n\nCheck if the grid element is greater than time.If so we have to calculate the wait by ((grid[newRow][newCol] - newTime + 1) / 2 )*2.\n\nIncrement the newTime with the wait.\n\n    if(grid[newRow][newCol]>newTime)\n    {\n        int wait=((grid[newRow][newCol] - newTime + 1) / 2 )*2;\n        newTime+=wait;\n    }\n\nIf we reach the bottom right, then newRow is equal to rows -1 and newCol is equal to cols-1, so return the newTime calculated so far.\n\n    if(newRow==rows-1 && newCol==cols-1)\n    {\n        return newTime;\n    }\n\nUpdate seen of the newRow and newCol to be true and insert the processed element\'s newTime, newRow and newCol to the priorityQueue.\n\n    seen[newRow][newCol]=true;\n    pq.offer(new int[]{newTime,newRow,newCol});\n\n**Returning the value**:\n\nReturn the newTime which is calculated if we reach the bottom right of the grid.Otherwise , return -1. \n\n    return -1;\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- ***Time complexity***: **O((rowsxcols).log(rowsxcols))**.\n        rows -> number of rows in the grid.\n        cols -> number of cols in the grid.\n\nEach cell is processed once and operation on priority Queue takes \n**O((rowsxcols).log(rowsxcols))**.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- ***Space complexity***: **O(rowsxcols)**.\n        rows -> number of rows in the grid.\n        cols -> number of cols in the grid.\n\nSpace is used for priority Queue and the seen array which is almost\n  \n   PriorityQueue = O(rowsxcols).\n   seen array    = O(rowsxcols).\n\n   Hence the total space is **O(rowsxcols) + O(rowsxcols) = O(rowsxcols)**.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    private static final int[][] MOVES={{-1,0},{0,1},{1,0},{0,-1}};\n    public int minimumTime(int[][] grid) {\n        int rows=grid.length;\n        int cols=grid[0].length;\n\n        if(grid[0][1]>1 && grid[1][0]>1)\n        {\n            return -1;\n        }\n\n        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);\n        boolean[][] seen=new boolean[rows][cols];\n\n        pq.offer(new int[]{0,0,0});\n        seen[0][0]=true;\n\n        while(!pq.isEmpty())\n        {\n            int[] curr=pq.poll();\n            int time=curr[0];\n            int row=curr[1];\n            int col=curr[2];\n\n            for(int[] dir:MOVES)\n            {\n                int newRow=row+dir[0];\n                int newCol=col+dir[1];\n\n                if(newRow<0 || newRow>=rows || newCol<0 || newCol>=cols || seen[newRow][newCol])\n                {\n                    continue;\n                }\n                int newTime=time+1;\n\n                if(grid[newRow][newCol]>newTime)\n                {\n                    int wait=((grid[newRow][newCol] - newTime + 1) / 2 )*2;\n                    newTime+=wait;\n                }\n\n                if(newRow==rows-1 && newCol==cols-1)\n                {\n                    return newTime;\n                }\n                seen[newRow][newCol]=true;\n                pq.offer(new int[]{newTime,newRow,newCol});\n            }\n        }\n        return -1;\n    }\n}\n```
['Array', 'Heap (Priority Queue)', 'Matrix', 'Java']