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

0:00 - Read the problem
0:30 - Drawing Explanation
14:26 - Coding Explanation
20:24 - Optimized Explanation

leetcode 2577

#neetcode #leetcode #python

[vitruvius]

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.

[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.

[nilfm]

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.

[myyfstz]

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.

[Explore-Everything]

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

[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.

[AnuragKumar-mwes]

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

[bgfreakn]

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

[AnivMazumder-cu]

Amazing, especially the last insight!!

[omdandade]

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 .

[lian]

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 :)

[victorb]

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.

[floriankubiak]

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

[maheshj]

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)

[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.

[hossammenem]

Thank you Mr. Max Tennyson for this informative video

[ronbuchanan]

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

[giorginho-o]

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

[kingheisenberg]

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

[mrf]

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.