Thanks for the good explanation! I kept exceeding the time limit without the trick of enqueuing each node at most twice. One more optimisation: since all edges are bidirectional, there are only 2 possible cases for the second shortest path. Let's call the shortest path A and suppose it goes over M edges. Either there is a longer path B that goes over M+1 edges, or we take path A and then at the end go to any node and back. So the second shortest path is always either 1 or 2 edges longer than the shortest path. You can apply this to quit BFS early -- if you found a shortest path, finish processing that layer, and exit the while loop. If the final node is in the queue, there is a path with M+1 edges. Otherwise, the second shortest path is M+2 edges. You can convert number of edges to time at the very end.
Hi NeetCodeIO. I think there is a problem in this code where the code can get stuck by visiting non final nodes two times(at different times) and exit out of the loop without returning inside the loop. This happened to me with the first example and I printed the visit_times dict outside the while loop and I got this value "defaultdict(, {1: [0, 6], 2: [3, 13]})"
class Solution: def secondMinimum(self, n: int, e: List[List[int]], t: int, c: int) -> int: a,b,q=defaultdict(list),defaultdict(lambda:[0]),deque([(1,0)]) for x,y in e: a[x].append(y); a[y].append(x) while q: v,d=q.popleft() if(d//c)%2:d+=c-(d%c) d+=t for u in a[v]: if (f:=b[u])[-1]!=d and len(f)
Welp I realized that I was adding nodes again and again in the queue but couldn't figure out a proper way to prevent it. NeetCode to the rescue as always :)
@NeetCodeIO On line 23, why would `nei_times.append(cur_time)`? I think the `cur_time` is still for `node`, not for `nei`, since we have cur_time updated at the end of while loop?
I was wondering just how are you able to solve every question and just exactly much time does it take for you to solve them ?? cause if I take it upon myself to solve these it would easily take my whole day and even then it's not guaranteed that I would solve it 😥
I never understood why BFS works and why the edge weight is unit. The weight of the each edge can either be the default time or longer if you at red light. Clearly edge weight can change dynamically depending on the state
Hey neetcode! can you please also start uploading solution tutorials for leetcode , codeforces etc contests questions (like once a week or twice), it will be very beneficial
I seriously dont understand why anybody would practice leet code problems anymore (aside for an interview). They are out dated now with advancements in LLMs. Its like asking accountants to use pen and paper for an interview instead of just letting them use excel.
@@NeetCodeIO Im just saying i never felt leet code was an accurate testament or assessment to being able to code. I've met so many people that were incredible at leet code problems, but hadn't actually built anything their whole lives. They had no idea how databases, HTTP, websockets, etc. worked. Anyone can get good a leetcode, that doesn't make you a good software engineer by any means. And with regards to LLMs, for me at least they are incredible and save me a ton of time. Just the other day I needed a function that would recursively filter a nested JSON. Instead of waisting my time thinking of this (or googling it), i asked chatGPT and it gave me a working solution in a minute. Maybe you consider figuring out functions like this important, but i dont. I consider creating things for clients in order to make money important. Nobody in the real world cares about how quickly you solved a algorithm, they care about what you deliver.
Congrats on the grass-touching :)
💚
Michael Cole: The streak.. is ov-
Neetcode-: Hold my video!
I am happy that somehow i figured out this math part by myself.
Thanks for the good explanation! I kept exceeding the time limit without the trick of enqueuing each node at most twice. One more optimisation: since all edges are bidirectional, there are only 2 possible cases for the second shortest path. Let's call the shortest path A and suppose it goes over M edges. Either there is a longer path B that goes over M+1 edges, or we take path A and then at the end go to any node and back. So the second shortest path is always either 1 or 2 edges longer than the shortest path. You can apply this to quit BFS early -- if you found a shortest path, finish processing that layer, and exit the while loop. If the final node is in the queue, there is a path with M+1 edges. Otherwise, the second shortest path is M+2 edges. You can convert number of edges to time at the very end.
Watch his videos even though i code in CPP. Just for the logic he provides like no one else on you tube.
making sure the visiting twice each node is the trickiest part here and that's where i got stuck. Thanks for the explanation.
Hi NeetCodeIO. I think there is a problem in this code where the code can get stuck by visiting non final nodes two times(at different times) and exit out of the loop without returning inside the loop. This happened to me with the first example and I printed the visit_times dict outside the while loop and I got this value "defaultdict(, {1: [0, 6], 2: [3, 13]})"
been waiting for this one
pls make a vid on Count the Number of Substrings With Dominant Ones
Thank you for this video!! I just realized I was messing up this part only - 19:43
this code seems wrong because we are visiing adjacent nodes of root node at time zero while we should be visiting them at time 3
Nice work bro. 👏
What a clean explanation on youtube.... Realy liked your every video.... From where you have learnt
class Solution:
def secondMinimum(self, n: int, e: List[List[int]], t: int, c: int) -> int:
a,b,q=defaultdict(list),defaultdict(lambda:[0]),deque([(1,0)])
for x,y in e: a[x].append(y); a[y].append(x)
while q:
v,d=q.popleft()
if(d//c)%2:d+=c-(d%c)
d+=t
for u in a[v]:
if (f:=b[u])[-1]!=d and len(f)
Welp I realized that I was adding nodes again and again in the queue but couldn't figure out a proper way to prevent it. NeetCode to the rescue as always :)
I am also thinking what is condition to prevent addition in queue because this will gonna be tle
can't thankyou enouf, ur true saviour,
keep up the awesome work @NeetCode
@NeetCodeIO
On line 23, why would `nei_times.append(cur_time)`?
I think the `cur_time` is still for `node`, not for `nei`, since we have cur_time updated at the end of while loop?
I was wondering just how are you able to solve every question and just exactly much time does it take for you to solve them ??
cause if I take it upon myself to solve these it would easily take my whole day and even then it's not guaranteed that I would solve it 😥
thank you, NeetCode
you a g, thanks for uploading
Thank you for the video! So clear now. You de best!
Thank you for the daily !
I never understood why BFS works and why the edge weight is unit. The weight of the each edge can either be the default time or longer if you at red light. Clearly edge weight can change dynamically depending on the state
Yes but the wait time will apply evenly to every single node within a given "level" of the BFS.
@@NeetCodeIO Ahh I think I understand now... many thanks!
Hey neetcode! can you please also start uploading solution tutorials for leetcode , codeforces etc contests questions (like once a week or twice), it will be very beneficial
It's all fun and games. Until the grass touches back...
Hey, neetcode, please solve today's contest's Q3
Java Solution
class Solution {
public int secondMinimum(int n, int[][] edges, int time, int change) {
Map map = new HashMap();
for (int i=1;i
POV: you have 30 minutes to solve this and the interviewer says it is trivial
Our savior :3
Mandal apla ahbhari ayhai
can you slove the problem number 1687 in leetcode
saw question gave up
Why DFS gives TLE but BFS doesn't?
Shortest path is more efficient with BFS
🙂
10:20 as an asian I can't relate sorry
I seriously dont understand why anybody would practice leet code problems anymore (aside for an interview). They are out dated now with advancements in LLMs. Its like asking accountants to use pen and paper for an interview instead of just letting them use excel.
Who do you think is gonna fix the bad code LLMs write? Definitely not you
@@NeetCodeIO Im just saying i never felt leet code was an accurate testament or assessment to being able to code. I've met so many people that were incredible at leet code problems, but hadn't actually built anything their whole lives. They had no idea how databases, HTTP, websockets, etc. worked. Anyone can get good a leetcode, that doesn't make you a good software engineer by any means. And with regards to LLMs, for me at least they are incredible and save me a ton of time. Just the other day I needed a function that would recursively filter a nested JSON. Instead of waisting my time thinking of this (or googling it), i asked chatGPT and it gave me a working solution in a minute. Maybe you consider figuring out functions like this important, but i dont. I consider creating things for clients in order to make money important. Nobody in the real world cares about how quickly you solved a algorithm, they care about what you deliver.
Bro’s brain is hacked
What a vision and thinking🫡