2577. Minimum Time to Visit a Cell In a Grid | Greedy | DIjkstras | Graph

[@Its_Shubham_Negi]

Bhaiya, nowadays I miss your excitement while solving the problems, but now you seem a bit more serious. I guess it's the effect of corporate life 💔

[@saikishanrao4150]

first youtuber who explain the code in java finally understood the code thanks bruh

[@Moin-f6w]

great explanation. i was almost there thank u

[@devendrasinghnegi3425]

❤

[@Its_Shubham_Negi]

Thanks bhaiya❤

[@PRANAVMAPPOLI]

Why we are not checking is there a better other option ro reach a cell or not. Here we are just use a visited set, buy usually im dijakastra we will compare if crntTime

[@vaibhavyadav3301]

You can also do that here this approach is also making sure the same thing. my code-> class Solution { class Triplet{ int x; int y; int dist; Triplet(int x,int y,int dist){ this.x=x; this.y=y; this.dist=dist; } } boolean isValid(int x,int y,int m,int n ){ if(x>=m || y>=n || x=2) { return -1; } int[][] distance=new int[m][n]; for(int i=0;i{ return a.dist-b.dist; }); pq.add(new Triplet(0,0,0)); while(pq.size()>0){ Triplet t=pq.remove(); int x=t.x; int y=t.y; int dist=t.dist; if(x==m-1 && y==n-1) return dist; for(int i=0;i=grid[x_new][y_new]){ currTime=dist+1; } else if((grid[x_new][y_new]-dist)%2==0){ currTime=grid[x_new][y_new]+1; } else{ currTime=grid[x_new][y_new]; } if(distance[x_new][y_new]>currTime){ distance[x_new][y_new]=currTime; pq.add(new Triplet(x_new,y_new,currTime)); } } } } return distance[m-1][n-1]; } }

[@PRANAVMAPPOLI]

@@vaibhavyadav3301 If we maintain a visited set , then a node wont revisited again , in dijkastra , a node should revisit , if we can reach the same node with lesser time . How this is getting ensure in the approach he mentioned {with visited}

[@vaibhavyadav3301]

Like if you have removed the node from minheap say from coordinates 2,2 then that will be the minimum time to reach that node, minheap actually makes sure that when a node is removed the distance(time in this case) is minimum to reach that node, we actually updates the distance array or vector when it is not visited at that node when it has Integer.MAX_VALUE at that idx. Basically what i want to say is if a node is removed from minheap, its distance is GUARANTEED to be the minimum possible distance from the source node, you can observe that by yourself we always processed the shorted distance node in minheap first. Hope that helps

[@goldenx2417]

Bhaiya please give code part of cpp also

[@Sarthak2421]

class Solution { public: #define P pair //time , i , j; int minimumTime(vector& grid) { if(grid[0][1] > 1 && grid[1][0] > 1) return -1; int n = grid.size(); int m = grid[0].size(); vector distance = { {0,1} , {1,0} , {-1,0} , {0,-1} }; vector visited(n , vector (m,0)); priority_queue< P , vector , greater> pq; pq.push({0,{0,0}}); while(!pq.empty()) { auto top = pq.top(); pq.pop(); int time = top.first , currRow = top.second.first , currCol = top.second.second; if(visited[currRow][currCol]) continue; visited[currRow][currCol] = 1; if(currRow == n-1 && currCol == m-1) return time; for(auto &dir : distance) { int nextRow = currRow + dir.first; int nextCol = currCol + dir.second; if(nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m || visited[nextRow][nextCol]) continue; int waitTime = ( (grid[nextRow][nextCol] - time) % 2) == 0 ? 1 : 0 ; int newTime = max(grid[nextRow][nextCol] + waitTime , time + 1); pq.push({ newTime , { nextRow, nextCol}}); } } return -1; } };

[@jigarthakor3939]

Excitement kaha gaya bhai else thodi chalega...!

[@Zomb-zj4ip]

goldman sachs kyu chod diya bhai

[@naturesrevolution]

one doubt what happen if gridvalue is greater than time (int cycleType = ((grid[nextRow][nextCol] - time) % 2 == 0) ? 1 : 0;) this line won't work then .. we should use Math.abs here?