Minimum Time to Visit a Cell In a Grid - Leetcode 2577 - Python

[@nilfm99]

For intuition on the explanation at the end, picture the grid as a chess board alternating white and black squares. It is clear then that each color has a corresponding parity.

[@vitruvius1202]

Hey Neetcode, can you please make a video about transitioning from mediums to hard? The biggest focal point in transitioning from easy to mediums was algorithm understanding. But I'm having issues with solving hard problems even though I understand those same algorithms(algorithms: sliding window, dp, etc.) that got me from solving easy to solving mediums. I know you can make an argument that if I can't solve hards, then I clearly don't understand the algorithms I'm working with. But I feel the answer is more nuanced and you'd be able to give valuable insights / strategies.

[@satviksrinivas8764]

Hi, I know this question was asked to NeetCode but I just wanted to share that in my experience the key to solving hards is recognizing those little aha moments. In my opinion what makes hard problems hard is that you need to know all the algorithms as you alluded to but each problem has a little aha moment where you need to think outside the box. For example, in this problem the aha moment would be the modular arithmetic part. In other problems it's recognizing that the XOR operator has a certain special property or realizing that you need to use two heaps instead of one, etc... But if you do a lot of these hards and make note of these aha moments I think they start to feel more tangible.

[@vitruvius1202]

@@satviksrinivas8764 Thanks for chiming in. Seems like the actual answer is the most obvious one, which is "Do more hards, and the patterns become more graspable."

[@Pippiwazza]

This becomes conceptionally a bit easier to think through, if you preprocess the grid by adding 1 to the cells that can only be reached 1 second after the time value they contain. Then you dont need to bother at all anymore about the parity thing.

[@BlunderArmour]

Yeah, no way I was going to come up with that logic of finding the time it takes to visit the next cell. Justified hard.

[@victorb6962]

The solution is missing important observation and a proof of the observation on which the correctness of the solution relies. For example, consider the case of a cell (i, j) that can be reached at time 10 from its left neighbor (i, j - 1), which is reachable at time 7, and the same (i, j) can be reached at time 11 from its upper neighbor (i - 1, j), which is reachable at time 8. If the right neighbor (i, j + 1) has grid[i][j + 1] == 12, then the proposed solution wouldn't work because (i, j) will be popped from the heap with time of 10 and marked as visited and so it's right neighbor would get assigned time 13, while when (i, j) will be popped from the heap the second time with time of 11 it's right neighbor will not get assigned correct time 12 because (i, j) is marked as visited. But the above example isn't possible due to the crucial observation that for every cell (i, j) it can be reached from (0,0) via any path only at odd times or only at even times. And so the above example isn't possible under this observation.

[@fahimimtiaz2153]

bro is the face of consistency

[@user-my6yf1st8z]

thanks, you jinxed it. The man can't be seen 2 days in a row

[@AnivMazumder-c1u]

Amazing, especially the last insight!!

[@user-my6yf1st8z]

thanks boss, tried to solve this problem implementing the yesterday's solution, but catched WA in tests. Didn't even catch that it's possible to go back and forth.

[@AnuragKumar-mw6es]

You are really awesome. Love your content. Cannot image a world without Neetcode.

[@Explore-Everything]

you are great bro i did not understood the solution but your explanation is making easy step by step

[@MP-ny3ep]

Very beautifully explained!

[@ap2s2000]

Happy Thanksgiving Neet!

[@b1gfreakn678]

Off topic to this video, but I’d love to see you solve some Advent of Code puzzles starting in a couple days!

[@lian1238]

i wrote 100 lines of code for 2 hours and got a max time exceeded error. thank you neetcode for simultaneously aspiring and making me feel dumb. mostly aspiring :)

[@Zero-ui4ep]

Awesome as always!

[@floriankubiak7313]

I believe this was in a contest this month. I really have to start learning graph algorithms :)

[@kane-m9o]

and i should too!!

[@omdandade8245]

In both yesterday's and today's problem, while implementing the Dijaktras algorithm, you won't update and re-push a node if there exists a shorter way to reach it (you just ingore it 'cause its visited). yesterday I got TLE in Java if I don't do it .

[@maheshj01]

Small improvement to eliminate if statement using bit manipulation wait = (abs(grid[nr][nc] - t) % 2) ^ 1 n_time = max(grid[nr][nc] + wait, t + 1)

[@hossammenem7396]

Thank you Mr. Max Tennyson for this informative video

[@PurpleDaemon_]

I knew the solution would be related with Greedy, but how do you decide what to pick as the Priority Key (the first element of the heap arrays)? I've tried using is_back_path and is_back_direction, to prefer movement toward the target, but how did you come up to the min_reach_cost solution? Is there a hint, or do you just have to know that such an option exists? BTW not sure if this really helps, but in the final solution I iverted x and y in the heap to again prefer path closer to the target.

[@mukherjee.p]

We love some hard problems!

[@g2gsoldchannel]

When I see you with the red shirt on the thumbnail, that's when I know I'm cooked for today

[@viswes8258]

I just noticed bro uses green shirt for easy, light green for medium and red for hard with same flowers design! 😭😂

[@kingheisenberg674]

is it even possible to solve it within time constraints of an interview or an OA?

[@PurpleDaemon_]

In conclusion, this is a regular greedy algorithm that can be written in couple minutes. The whole point is to select the right Priority Key. But unfortunately, I don't see an algorithm to determine it. So IMHO this problem can be solved in minutes (if you know the right PK) or not solved at all.

[@EverAfterBreak2]

I highly doubt you will see this in an OA

[@ronbuchanan5432]

what if the upper-left cell isn't 0? Let's say it was 100. Is it a valid configuration of the grid?

[@devmahad]

thanks :)

[@icvetz]

Is anyone else getting TLE for case 3?

[@baophi2322]

me

[@baophi2322]

You might forgot the visit set!

[@mrf92]

why to use viseted with dijkstra? first you say that you are doing a variation of dijkstra and then said it is common to use visited set in BFS.Apparently, these two algorithms are not same. please clarify why do you use visited with dijkstra.