Great video! I think the part about the graph potentially gaining a cycle is wrong. The 5th constraint (1 < queries[i][1] - queries[i][0]) guarantees that every edge will be pointing forward. Because of this constraint, we always have a topological ordering of the graph (the nodes from 0 to n-1), and thus, the graph doesn't have any cycles. Having a visited set is a great optimization (and actually needed to pass all leetcode tests) to prevent exploring the same node more than once, but it's not strictly necessary for the algorithm to terminate, as after a finite number of iterations, it will reach the last node. Your videos are really helping me learn DSA, thank you so much for your work!
small correction in my opinion, visit is a set() of integers, so why add (0, 0) initially, by the way it works fine with initial value as 0, so visit.add(0) works
Just as an additional comment, this problem is a very good candidate for Dijkstra's algorithm. For each query, we actually need to recalculate costs from the source node to the n-1. This also will exclude any possible cycle problem because, with Dijkstra, we schedule to traverse only nodes whose distance is lower than the calculated shortest distance for this node, hence if we go back at some point - the cost will be higher than before and we ignore this edge. Of course, Mr. NeetCode knows that, just a comment for fellow leetcoders passing by :)
neetcode, i created this plan: i will only start the daily problem, when you post a video. First i will try to solve it myself without watching your vid, but more likely i will fail and i will watch your explanations. My leetcode life is connected to your channel. Notification is ON. I'm coming for that belt. No motivation, only discipline. lesss gooo
Can be optimized a little with DP. You keep track of the shortest distance to each node, and only run the bfs from the end of the new road if the distance to the end of the new road decreases.
Thank you so much for your videos!!! I kid you not, my initial solution was almost the same as your apart from the variable names, it almost felt like dejavu. Your videos have taught me everything I know about DSA that's for sure
please go to live while solving the problems instead of videos it will help some beginners like me to learn by the way your teaching and approach to the problem was awesome
The graph will not get cyclic, it sustains acyclic theoretically - redundant traversal feels it appear like a cycle - I believe thats what he is trying to mention - it consumes more time - therefore you can use a set to discard the visited paths
I think we can assume that graphs can never become cycle because its a directed graph and the direction is always from left to right , though visited set would help in avoid the same calculation again and again
@neetCodeIO: I dont think cycle can be formed. unidirectional can be considered as DAG initially and new queries adds an edge in forward direction. so its still DAG and no cycles are formed. inorder it to be a cycle there has to be atleast a backward edge right? which is not the case. so no cycle is possible.
In the adjacency list, adj[i] is the list of all nodes that the node i points to. At the beginning every node i points to i+1, so adj[i] is just the list [i+1].
I solved the problem using bfs, but I'm more curious about the workaround for minHeap, can someone explain the solution for minHeap ? and why minHeap looks more efficientally?
bfs traverses level by level, i.e. all nodes that can be reached by a path with length 1, 2, 3... so on. so the moment you encounter the node you want for the first time, its the shortest path
I dont understand either. Because for Dijkstra's algorithm we only consider the nodes with shortest steps / distance first ensuring we reach n-1 with least steps. But how does BFS ensure that we reach n-1 with min steps ? Maybe the shortest distance we encounter comes later ?
@@bored_bread Dijkstra's algorithm has nothing to do with this. Dijkstra is usually used when the edges are *weighted* and here that is NOT the case. The reason why BFS ensures that node n-1 will be reachesd in minimum amount of steps is that if we go level by level, we'll get to explore minimum amount of needed steps for the current level(node) every step of the way and then once we get to our n-1 node(last level), we'll know that the Shortest distance is the minimum distance out of every node that feeds into the current node_n-1 plus one(plus the last node itself). In other words - Check min-distances of every nodes that FEEDS into the current one and take the minimum out of those and then add 1(to count the current node itself). Let's check an example: (Edit: UA-cam has weird formatting rules, so I had to change to "drawing" a bit") __________ / | / v 0 -> 1 -> 2 -> 3 We'll know that to come to node_0, starting from node_0, the min-distance is CERTAINLY a ZERO, meaning the total amount of "jumps" we have to do to get to n from node_0 to target(node_0) is zero(0). Now we are at level_1(i.e. node_1). Which nodes feed into the current node_1? Well, only one node(node 0). Okay - What is the min-distance to come to node_0, starting from node_0? It's one(1) node, as we've seen in the previous paragraph above. Now we know that min-distance for node_1 is: min-distance of node_0 +1(plus one because we're jumping from node_0 to current node_1) Therefore, min-distance for node_1 is: one(1) Now we are at level_2(i.e. node_2). How many nodes feed into the current node? Only one node(node_1). What is the min-distance to come to node_1, starting from node_0? It's one(1), as we've seen in the previous paragraph above. Now we know minimum distance for node_2 is: min-distance of node_1 +1(plus one because we're jumping from node_1 to current node_2 ) Therefore, min-distance for node_2 is: two(2) No we get to the nteresting part. Now we are at level_3(i.e. node_3) How many nodes feed into the current node? Two nodes(node_2 and node_1). What is the min-distance to come to node_2, starting from node_0? It's two(2). What is the min-distance to come to node_1, starting from node_0? It's one(1). Which one of those is the minimum? It's one(1), therefore we know that the min-distance for node_3 is: min-distance of node_1 + 1(because we're jumping from node_1 to current node_3) Answer --> min-distance for node_3 is: two(2). So to come from node_0 to node_3, we need two "jumps". The picture makes this clear. We go from node_0 to node_1 and then from node_1 to node_3, which is a total of two(2) "jumps". And that is the answer we needed. That's why BFS guarantees we'll have the minimum distance.
Man, your uploads have gotten faster ever since you said you were not going to upload for a while. Can't thank you enough!
Great video! I think the part about the graph potentially gaining a cycle is wrong. The 5th constraint (1 < queries[i][1] - queries[i][0]) guarantees that every edge will be pointing forward. Because of this constraint, we always have a topological ordering of the graph (the nodes from 0 to n-1), and thus, the graph doesn't have any cycles. Having a visited set is a great optimization (and actually needed to pass all leetcode tests) to prevent exploring the same node more than once, but it's not strictly necessary for the algorithm to terminate, as after a finite number of iterations, it will reach the last node. Your videos are really helping me learn DSA, thank you so much for your work!
small correction in my opinion, visit is a set() of integers, so why add (0, 0) initially, by the way it works fine with initial value as 0, so
visit.add(0) works
Gratitude button.Thanks GOAT-Code!
Just as an additional comment, this problem is a very good candidate for Dijkstra's algorithm. For each query, we actually need to recalculate costs from the source node to the n-1. This also will exclude any possible cycle problem because, with Dijkstra, we schedule to traverse only nodes whose distance is lower than the calculated shortest distance for this node, hence if we go back at some point - the cost will be higher than before and we ignore this edge. Of course, Mr. NeetCode knows that, just a comment for fellow leetcoders passing by :)
neetcode, i created this plan:
i will only start the daily problem, when you post a video.
First i will try to solve it myself without watching your vid, but more likely i will fail and i will watch your explanations.
My leetcode life is connected to your channel.
Notification is ON.
I'm coming for that belt.
No motivation, only discipline. lesss gooo
Can be optimized a little with DP. You keep track of the shortest distance to each node, and only run the bfs from the end of the new road if the distance to the end of the new road decreases.
Thanks for the video. I dont think there will be a cycle since constraints include "0
Viisted set looks off. Initially you are adding a tuple to it but in the neighbours loop, you are adding only the neighbour and not the length.
hi neetcode thanks to your videos I can ace my interviews but I still can't get a job but at least I can ace my interviews!!!!!
Thank you so much for your videos!!! I kid you not, my initial solution was almost the same as your apart from the variable names, it almost felt like dejavu. Your videos have taught me everything I know about DSA that's for sure
The visit set is not to prevent cycles, because they are excluded in the restrictions. But I get a TLE without it.
please go to live while solving the problems instead of videos it will help some beginners like me to learn by the way your teaching and approach to the problem was awesome
The graph will not get cyclic, it sustains acyclic theoretically - redundant traversal feels it appear like a cycle - I believe thats what he is trying to mention - it consumes more time - therefore you can use a set to discard the visited paths
I think we can assume that graphs can never become cycle because its a directed graph and the direction is always from left to right , though visited set would help in avoid the same calculation again and again
@neetCodeIO: I dont think cycle can be formed. unidirectional can be considered as DAG initially and new queries adds an edge in forward direction. so its still DAG and no cycles are formed. inorder it to be a cycle there has to be atleast a backward edge right? which is not the case. so no cycle is possible.
This solution us going TLE in java
Why "[[i + 1] for i in range(n)]" instead of "[[i] for i in range(n)]". I dont really understand
In the adjacency list each node points towards the next one, in this way you will have 0->1, 1->2 etc.
In the adjacency list, adj[i] is the list of all nodes that the node i points to. At the beginning every node i points to i+1, so adj[i] is just the list [i+1].
I solved the problem using bfs, but I'm more curious about the workaround for minHeap, can someone explain the solution for minHeap ? and why minHeap looks more efficientally?
THANKS!
the constraints says that query 0 will always be less than query 1, how can we have cycles?
I found out that we use a visit set bcs we only care to visit city i the first time since it was the shortest path to get there.
why are you adding (0,0) to the visited set instead of just 0? later we are just adding the neighbour nodes
may be by mistake he might have written, but i think we will just add 0 in visited set
i spent 2 hours trying to solve this task trough DFS.
always use bfs for shortest path algos
I ended up implementing a full Dijkstra's traversal because my brain defaults to that now and I can't see the simpler method. 😶
I don't understand how this makes sure to return the shortest path
because you search from 0 to n - 1.
bfs traverses level by level, i.e. all nodes that can be reached by a path with length 1, 2, 3... so on. so the moment you encounter the node you want for the first time, its the shortest path
I dont understand either. Because for Dijkstra's algorithm we only consider the nodes with shortest steps / distance first ensuring we reach n-1 with least steps. But how does BFS ensure that we reach n-1 with min steps ? Maybe the shortest distance we encounter comes later ?
@@bored_bread Dijkstra's algorithm has nothing to do with this. Dijkstra is usually used when the edges are *weighted* and here that is NOT the case.
The reason why BFS ensures that node n-1 will be reachesd in minimum amount of steps is that if we go level by level, we'll get to explore minimum amount of needed steps for the current level(node) every step of the way and then once we get to our n-1 node(last level), we'll know that the Shortest distance is the minimum distance out of every node that feeds into the current node_n-1 plus one(plus the last node itself).
In other words - Check min-distances of every nodes that FEEDS into the current one and take the minimum out of those and then add 1(to count the current node itself).
Let's check an example: (Edit: UA-cam has weird formatting rules, so I had to change to "drawing" a bit")
__________
/ |
/ v
0 -> 1 -> 2 -> 3
We'll know that to come to node_0, starting from node_0, the min-distance is CERTAINLY a ZERO, meaning the total amount of "jumps" we have to do to get to n from node_0 to target(node_0) is zero(0).
Now we are at level_1(i.e. node_1).
Which nodes feed into the current node_1? Well, only one node(node 0).
Okay - What is the min-distance to come to node_0, starting from node_0?
It's one(1) node, as we've seen in the previous paragraph above.
Now we know that min-distance for node_1 is:
min-distance of node_0 +1(plus one because we're jumping from node_0 to current node_1)
Therefore, min-distance for node_1 is: one(1)
Now we are at level_2(i.e. node_2).
How many nodes feed into the current node? Only one node(node_1).
What is the min-distance to come to node_1, starting from node_0?
It's one(1), as we've seen in the previous paragraph above.
Now we know minimum distance for node_2 is:
min-distance of node_1 +1(plus one because we're jumping from node_1 to current node_2 )
Therefore, min-distance for node_2 is: two(2)
No we get to the nteresting part.
Now we are at level_3(i.e. node_3)
How many nodes feed into the current node? Two nodes(node_2 and node_1).
What is the min-distance to come to node_2, starting from node_0? It's two(2).
What is the min-distance to come to node_1, starting from node_0? It's one(1).
Which one of those is the minimum? It's one(1), therefore we know that the min-distance for node_3 is:
min-distance of node_1 + 1(because we're jumping from node_1 to current node_3)
Answer --> min-distance for node_3 is: two(2).
So to come from node_0 to node_3, we need two "jumps". The picture makes this clear.
We go from node_0 to node_1 and then from node_1 to node_3, which is a total of two(2) "jumps".
And that is the answer we needed. That's why BFS guarantees we'll have the minimum distance.
nobody understands, but it's provocative! it gets people going!