Critical Connections in a Network - Leet Code Hard Problem

Hey guys I made an instagram my name is @active_programmer_girl for those who want to connect. I get a lot of messages from people on LinkedIn but I don't check it that often.

[@talivanov93]

Thank you so much for the explanation! For those of you who want the solution written: class Solution { private int currentTime = 0; public List criticalConnections(int n, List connections) { { int[] times = new int[n]; int[] lowTimes = new int[n]; boolean[] visitedNodes = new boolean[n]; List ans = new ArrayList(); ArrayList[] graph = new ArrayList[n]; for(int i = 0; i < graph.length; i++) { graph[i] = new ArrayList(); } for(List connection: connections) { graph[connection.get(0)].add(connection.get(1)); graph[connection.get(1)].add(connection.get(0)); } for(int i = 0; i < n; i++) { visitedNodes[i] = false; } dfs(graph, 0, -1, times, lowTimes, visitedNodes, ans); return ans; } } private void dfs(ArrayList[] graph, int currentNode, int parentNode, int[] times, int[] lowTimes, boolean[] visitedNodes, List ans) { visitedNodes[currentNode] = true; times[currentNode] = lowTimes[currentNode] = currentTime++; for(int neighbourNode: graph[currentNode]) { if(neighbourNode == parentNode) continue; else if(!visitedNodes[neighbourNode]) { dfs(graph, neighbourNode, currentNode, times, lowTimes, visitedNodes, ans); lowTimes[currentNode] = Math.min(lowTimes[currentNode], lowTimes[neighbourNode]); if(times[currentNode] < lowTimes[neighbourNode]) { ans.add(Arrays.asList(currentNode, neighbourNode)); } } else { lowTimes[currentNode] = Math.min(lowTimes[currentNode], lowTimes[neighbourNode]); } } } }

[@crisag.2698]

Thank you lol I forgot to do this!

[@aishwaryasharma974]

This was a very good explanation.I don't see a lot of representations from the females when it comes to coding and looking at you code makes me feel a little more confident about it. Thank you.

[@crisag.2698]

Thank you! That means a lot to me :)

[@lifeofme3172]

I agree to this comment. Go girl power, btw am a guy.

[@dakshkant3523]

After hours of watching the popular videos on this topic that have way too many views than yours, I stumble upon your video in my recommendations at midnight after it's been two weeks since I've given up this topic. All I can say is you did a job so good that I didn't have to replay even a single second to understand what you were explaining and now I have a good understanding of the algorithm as to why it works! Simply awesome you are, you made my day!

[@Cheesymultipatao]

Agreed.

[@ajayboseac01]

This is the best explanation of Tarjan's algorithm I have found in youtube.

[@Aman-eu1eh]

You should definitely start this channel to explain all problems of Amazon, you do it perfectly.

[@crisag.2698]

Hey that is a good idea! I might do that this weekend, thanks for the tips :)

[@nehascorpion]

Very well explained! After trying to get this problem via several videos and online articles, yours was the one that I could finally understand with utmost clarity. Thanks a ton and keep it up. You rock! :)

[@crisag.2698]

Thanks for the feedback everyone. I made an instagram @active_programmer_girl for people who want to connect. I get messages on LinkedIn but I don't check it too much.

[@mahendrajadav2286]

What's your real insta id??

[@nomaanhusain]

this felt so much like a real interview, well explained!

[@eduard7746]

Finallyyy, I was able to find a solution thanks to you, which is not using an additional stack. Thank you very much

[@Pruthvikajaykumar]

Can't believe this is your only programming video. Please do more, thank you

[@ganeshckm5246]

I couldn't find a better explanation for this problem than your video. Awesome stuff. Please do more videos :)

[@winghymliu]

great explanation, really appreciate going line by line to build the solution

[@daesk]

finally in good english and code explained. Thank you very much

[@duncansanya6992]

I found this question in an interview and it kicked me, though I did it with a slower algorithm, taking out each node and counting visited nodes. Tarjan' algorithm is much faster.

[@crisag.2698]

This would wreck me in an interview if I had never seen it prior

[@jacquelinepang7853]

@@crisag.2698 I am surprised that this question is poped during an interview coz this Tarjan algorithm is like: "you-know-it then you know, you-dont-know-it you will not get it in 40 minutes interview", not a good way to find smart engineers. Saying that your solution is very clear and concise and the closest to the general Tarjan implementation, really appreciate the walkthrough! Thank you!

[@prajwalasrivatsa1160]

Amazing explanation! Would not have been able to understand this code without it. Thanks and please make more videos on leetcode hard questions!

[@pariraja_smiles]

That's a good explanation crisa. Thanks for helping out :)

[@crisag.2698]

Hi Mani!!! :) Thanks for watching

[@venkatarohiththeeda7139]

Have searched a lot of sites for this algo! This was the best explanation so far.. Thanks a lot. Keep going :)

[@gourabdiptaghosh451]

I have seen some other explanations of this problem, and this one is the most crisp one. Great job Crisa, keep going. Wishes from India.

[@deus9246]

Finally got this! Thanks for sharing.

[@wj4352]

I was struggling with this problem earlier. Not any more. Nice explanation. Thanks!

[@wj4352]

this also works. In else { lowTime[currentNode] = Math.min(lowTime[currentNode], lowTime[neighbor]); }

[@niharikapatil902]

This is an amazing video !! You GO, GIRL!

[@crisag.2698]

Thank you Niharika I appreciate the kind words haha :)

[@21bhaswanthreddy25]

Good work and Great Explanation 😊👌

[@veronicatian7254]

Hi, please do more! You did an excellent job explaining this problem! Thank you, helped a lot!

[@crisag.2698]

Thank you Veronica I appreciate the feedback!

[@MrArpit1234]

Why is a visited node make a edge BackEdge? As per the definition it should be CROSS EDGE And the BACK EDGE would be one in "stack and visited ". Is it just because its a non directed graph ? So we dont need to use stacks ?

[@wayynec]

Thank you for this video. Super clear explanation!

[@mihir7]

Really awesome explanation, one of the best videos I found on this topic. Thanks much!

[@chintalapativenkataramarahul]

Such a great explanation!! Many, many thanks to you for this.

[@junkoe3808]

Hey, this is my second comment, for some reason I cannot find the first one in the list. Basically, I was surprised by your channel. The fact that it goes from a good display of piano skills to a random programming problem is interesting. I like various things, puzzles are among them and there's a small interest in music which is slowly developing (bought an electric piano). At this point, what I want to say with this is obvious. Would you like to chat? I don't have an instagram, but I use telegram and discord ( much less discord since I'm taking a break for it to study more).

[@Mike-ci5io]

I think one assumption skipped over in the beginning is the node values are bounded by the graph size [0 - n-1] that's why you used arrays otherwise you would have to use sets

[@ashuadkar]

Loved the video. Very easy to understand explanation. Can you cover more leetcode hard problems?

[@xinhuang7149]

I finally understand! Thank you Crisa!

[@crisag.2698]

Thank you for watching and I am happy to hear it helped instead of confused you more lol

[@soumyadeeproy6611]

Really good explanation !! I was looking for it

[@saurabhgujare6219]

so glad that I came across this video. 👏

[@generationnext4138]

Thanks for making this video. The way you explain as you code is really helpful to understand line by line. I really appreciate your efforts. One suggestion, if you could also explain the time and space complexities, it will be great. Thanks again and cheer up :)

[@crisag.2698]

Yes I will deff do that. More videos coming this weekend! Thanks for the feedback

[@fdm6334]

I had been waiting for someone to upload a good explanation to this problem and yours is it. That helped me understand Tarjan's algo, so thank you! Also, the typos in the end were so relatable. lol

[@crisag.2698]

Thank you! I'm glad to hear it helped. I was thinking of redoing it because I think I could've explained things better. And yes lol, I don't think I've ever submitted an answer to LC without at least one type 😭😂

[@fdm6334]

@@crisag.2698 To be honest I still don't fully understand line 30 in your code, why it's necessary, but I'm just going to watch it again until it makes complete sense. I think your explanation was pretty clear though. Just subscribed!

[@user-cq6os8tg4w]

when !visited[neighbor] is True: we take the min of the lowTimes[currentNode], lowTimes[neighbourNode] lowTimes[currentNode] = Math.min(lowTimes[currentNode], lowTimes[neighbourNode]); When !visited[neighbor] is False: we take the min of the lowTimes[currentNode], lowTimes[neighbourNode] lowTimes[currentNode] = Math.min(lowTimes[currentNode], visitedTime[neighbourNode]); Can't we take the min of lowTimes[currentNode], lowTimes[neighbourNode] both of the times. Does it makes any difference?

[@lakshaysharma8605]

That's really a fine explanation. Good Job !!

[@johnsheridan9880]

Crisa, thank you for this explanation. Well done!

[@crisag.2698]

Thank you John Sheridan - let me know if there's any problems you'd like to see :)

[@leowu5058]

Great explanation! Please make more coding videos, thank you!

[@cloud15487]

Thanks for the explanation. Were you able to take the Amazon online assessment?

[@crisag.2698]

No I just do these for fun because I'm weird like that. Have you?

[@cloud15487]

Crisa Gazzola I am going to but I am kind of scared, hence I am practicing a shit ton 😂

[@devashishsrivastava1132]

This solution is failing for [[0,1], [0,2], [1,2], [1,3], [3,4], [4,1]]. Here 1 is the critical connection point but critical connection list is empty. Can you please give it a try with the above input set. There are 5 nodes.

[@crisag.2698]

Thanks Devashish, I will check this out tomorrow, but assuming you are correct, good catch!

[@samisamee6119]

[[0,1], [0,2], [1,2], [1,3], [3,4], [4,1]], here 1 is an articulation point, but this solution is to find an edge, i.e., a critical connection

[@yoshi4980]

would you really be expected to come up with this in an interview? i created the graph in a similar way, but then i just looped through the edges, removed them and checked if i could still reach the destination. for example, if i remove edge (i,j), then i do a search from i to see if i can still reach j (or viceversa) if i can still reach j from i after removing edge(i,j), then it is not a critical connection the way i did a search was a BFS, but i timed out so i tried doing a BFS from both i and j at the same time, and checked when they met(i think i did it wrong so i'll have to check that out later, but this was the general approach i followed) would this still work? it seems much simpler but i think the time complexity is still very poor and would still time out :/

[@Lokeshkumar-ex4kd]

Great Explanation Crisa. kudos

[@umber3117]

Great explanation!!! Thanks for sharing.

[@adi_sekar]

Great explanation. Pls do more LC hard questions

[@abhishekiswalkar9084]

Thank you so much for the great explanation.

[@rajneeshyadav9728]

awesome explanation

[@montuedge]

@13:40 thank you, that makes sense

[@kaichenghu3826]

very good explanation!

[@minichang2215]

Your explanation is nice. But this solution cen be easier if you can find eges in cycles, and remove them, then remaining will be critical connections

[@pranavyeleti3499]

the solution is based on tarjans algorithim?

[@nairchannel3753]

Thank You . It was very helpful.

[@pinakisaha9917]

A great video. The explanation was pretty good. Keep it up. Spelling mistake of the variables happen to be all the time. Still awesome video. Keep it up

[@varunateru]

Perfect. Thank you for the video.

[@NikashKumar]

very well explained.

[@Jack_Callahan01]

Hold the fuckin phone. You play guitar, piano, and can code!?!?! Your impressing me and that is hard to do.

[@dmitrykarpenko2271]

IMO creating a Node class with all those values is more convenient.

[@siddharthsharma3679]

Hey Great Content, thank you =) qq, what would be the time and space complexity on this ?

[@shivanireddy4701]

O(V+E) time complexity as we are doing DFS.

[@binoy4814]

nice one!!

[@lilin3005]

You are a goddess!

[@dharamendraprajapati1301]

Great Explanation!!

[@Gggggg172eyeyeurhuwue]

Can anyone help me out here, can targen's algorithm be applied on undirected graphs as well, like here, what does an SCC mean in an undirected graph

[@aliarfath]

Still confused with line 32, how is visitedTime array helping us? thanks in advance. Can't we use Lowtimes array there?

[@ArpanPathak]

If you want intuitive explanation then watch this video kzbin.info/www/bejne/aoDGY5uLlLprmZo

[@siddheshswnt]

Good explanation. Keep it up!

[@crisag.2698]

Thank you!

[@ayonkar1534]

Nice. Can you also explain Minimum Knight Moves?

[@avinavpandey1671]

Crisa , could you share the code base as well > maybe a Github link with the code.

[@crisag.2698]

Yes I will be making a repo for these solutions, then I will come back to this comment and share the link.

[@datle5449]

Thanks

[@TheArmenianSolider65]

There's a great video by GeeksforGeeks that helps visualize this algo: kzbin.info/www/bejne/qpmvgox4od9leq8 Good work on the code btw Crisa. You currently interviewing for Amazon?

[@jayanttanwar4703]

Thanks. Make more videos.

[@davincipro9976]

It does not work

[@pouya2002]

Hey Do you want to start a virtual meet ups for solving Algorithms ? I was always in leetcode solving and practicing and I was think to create a meet up groups to actually get together weekly with others and think on new problems and teach and learn each others and basically get keep practicing algorithms and data structures.

[@subhamukherjee7213]

very well explained!. Awesome keep it up.

[@crisag.2698]

Thank you!

[@pradeepbalasundaram]

class Solution { boolean visited[]; List ans = new ArrayList(); Map graph = new HashMap(); int nodeRank[]; int time = 0; private void exploreDfs( int curr, int parent) { visited[curr] = true; int origTime = nodeRank[curr] = time++; for (int nei: graph.getOrDefault(curr, new ArrayList() ) ) { if(nei == parent) continue; if(!visited[nei] ) { exploreDfs(nei, curr); if(origTime < nodeRank[nei]) ans.add( Arrays.asList(curr, nei)); } nodeRank[curr] = Math.min( nodeRank[curr], nodeRank[nei] ); } } public List criticalConnections(int n, List connections) { for (List connection: connections) { graph.computeIfAbsent(connection.get(0), k -> new ArrayList()).add(connection.get(1)); graph.computeIfAbsent(connection.get(1), k -> new ArrayList()).add(connection.get(0)); } visited = new boolean[n]; nodeRank = new int[n]; exploreDfs(connections.get(0).get(0), -1); return ans; } }

[@hainguyenx]

wow. Smart and pretty. You are awesome.

[@subhashb3214]

Thanks for the explanation. Can you make company wise playlist.

[@jos6982]

so hard