Leetcode 1466 - REORDER ROUTES TO MAKE ALL PATHS LEAD TO THE CITY ZERO

[@NeetCode]

💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc

[@Bonnbon8]

i leetcoded my way to an ancient neetcode video

[@Federico-fz2tr]

facts

[@trh786fed]

I'm one my 200 something leetcode

[@amogchandrashekar8159]

And I just realised, I am your first subscriber. Way more to go!

[@RolopIsHere]

I just discovered this video and the first subscriber.

[@chandransh2813]

I just discovered this video, the first subscriber and also the person who commented on the first subscriber's comment.

[@chiragjoshi482]

@@chandransh2813 i just discovered this video, the first subscriber, the person who commented on the first subscriber's comment and the person who replied to the comment on first subscriber's comment.

[@alifakhreldin9590]

@@chiragjoshi482 i just discovered this video, the first subscriber, the person who commented on the first subscriber's comment and the person who replied to the comment on the comment that replied to the first subscriber's comment

[@mubshali7489]

@@alifakhreldin9590 I feel guilty for breaking the chain but it got too long. Kudos to neetcode for making our lives easier with his 4 yrs of hard work! love him!!

[@jameshamilton3484]

I found your videos about a week ago and found the explanations easy to understand and very helpful. It has quickly become a habit to come and check your channel when I'm stuck on LC

[@nw3052]

Same. Such a blessing that we can get it for free.

[@almasabdrazak5089]

I didn't understand how to solve it, decided to check your video , in 2:10 when you said we should check if neighbors of 0 can reach it I understood it's BFS and solved it without finishing the video , thank you

[@NeetCode]

That's great! Glad it was helpful 🙂

[@amogchandrashekar8159]

Wow man! Just wow! Usually i solve 3 problems in a contest, could not solve this today though :( The explaination is very clean and concise! Thank you so much. Subscribed!

[@NeetCode]

I appreciate the kind words! I'm definitely not a genius, but I love breaking down problems into their simplest form.

[@amogchandrashekar8159]

@@NeetCode Please continue doing videos! It would be really helpful for self taught programmers like me. Thanks.

[@lifeofadev]

for those who wonder why we're checking (neighbour, city). It's because having city -> neighbour (towards 0) at each level is the desired result ex. start from 0, its neighbours should have edges (neighbour, city) = (0, current_city), here current_city is 0's a neighbour city

[@rowanus116]

Here are several notes: 1. For anyone who has difficulty on understanding how to count the "reorienting roads", here is how: When we dfs the neigh: city, we always starts from root city(0), so the pair {neigh, city} must mean we can traverse back from the neigh to 0(root), so if it not represent in the connections, then it means we need to modify it, hence the count needs to be incremented. 2. The visited set is needed to avoid the infinitely loop when DFS. 3. Build the adjacent lists, which always required for these graph problems.

[@niteshmanem1997]

This was where Neetcode was created. His origin story

[@cosepeter2197]

Rest is history 😁

[@ngneerin]

In short: Create count variable to store count of change in direction required. Create an empty set named visited. Create set of the pairs named edges. Create map of all cities from 0 to given n and add their partner city to it's value in an array. Do a Depth First recursion, starting from 0. Add 0 to visited set and call recursion function by passing 0 as city. For each value, check if it is not in visited, then for each neighbour of the city check if there is no neighbour, city pair in edges, then increment count. Add neighbour to visited. Call recursion function by passing the neighbour as city. After the recursion return the count.

[@apoorvan4608]

your solution is easier than chat gpt's. gotta love the human brain!

[@HaoLi-tp8zl]

I have a question, if I don't create edges and use: if [neighbor, city] not in collections, why this will exceed time limit?

[@iOSDeepDive]

Edges is a set. When you search for a value in a set it is O(1). Searching for a value in an array like collections is O(n). dfs already makes it O(n), if you search again in collections it will be O(n * n) or O(n^2). If you use a set it is just O(n +1) or reduced to O(n)

[@tonyz2203]

Why do we add 0 to visited before calling the dfs(0)?

[@aa10259]

why we need to take both the possibilities if its directed graph. why line 16 ?

[@tobiahrex]

really clean & intuitive solution. Well done.

[@code7434]

Can you please solve hard leetcode problems , may be problems filtered after 1300 number . that are of recent 4-6 months.

[@kirillzlobin7135]

Amazing solution

[@MP-ny3ep]

Thank you! Awesome explanation!

[@deepaligarg2978]

Thanks for the explanation

[@niachungdupit8104]

What if graph has loop, and we can travel one cities through multiple path

[@gurazeez]

the question says n cities connected with n-1 roads, there cannot be a loop/cycle in the graph

[@Trizzi2931]

@@gurazeez what if there are 4 cities and 1->2, 2->3, 3->1 and no one is connected to the 0th city. Here every city is only connected through one path.

[@gurazeez]

@@Trizzi2931 read the last line of the question It's guaranteed that each city can reach city 0 after reorder This means that all the cities must be able to reach 0, this ensures that they are all cities are connected and will not be left out

[@Trizzi2931]

@@gurazeez all the cities can reach 0 too in the example I shared you just have to change the path from 1->2 to 1->0

[@gurazeez]

@@Trizzi2931 you do not understand the question, the question says that we have to reorient the roads, if there is a road from 1 to 2, then you can change its direction so that it now goes from 2 to 1, but you cannot make it go from 1 to 0 or any other node

[@mondayfootprint1280]

awesome explanation

[@arpitsinghal07]

Hi all, I've some experience in python but the 2nd statement's syntax, where he's initializing arguments seems novel to me. if someone knows it's technical definition pls reply, I'd like to search about it. btw, just discovered this channel and this guy is great.

[@WillFlores1]

this felt like i waas watching blue clues or dora everytime you asked me a questin andi solved it in my head

[@aumrudhlalkumartj1948]

Thanks

[@aditiraj306]

this solution is giving time limit exceeded now

[@yang5843]

class Solution { Map map = new HashMap(); Set set = new HashSet(); Set connects = new HashSet(); int rc = 0; public int minReorder(int n, int[][] connections) { for (int i=0;i

[@tofahub]

Not all heroes wear capes

[@pinkylover911]

I wonder how you are able to type with your mouse :)

[@priyanshudeep1008]

I think he is using a mechanical keyboard.

[@edwardteach2]

U a City God

[@NeetCode]

🙏

[@cagdasalagoz]

This question starts and ends at the first sentence of the definition.

[@danielsun716]

BFS FYI: def minReorder(self, n: int, connections: List[List[int]]) -> int: ''' start at city 0 list the original edges count the changes ''' edges = {(a, b) for a, b in connections} neighbors = {city: [] for city in range(n)} visit = set() changes = 0 # connect all nodes for a, b in connections: neighbors[a].append(b) neighbors[b].append(a) q = collections.deque([0]) visit.add(0) while q: city = q.popleft() for nei in neighbors[city]: if nei in visit: continue if (city, nei) in edges: changes += 1 q.append(nei) visit.add(nei) return changes

[@rsKayiira]

Great explanation of the solution but the BFS solution is much much much better than this

[@k.k.harjeeth5422]

from collections import defaultdict class Solution: def minReorder(self, n: int, connections: List[List[int]]) -> int: edges=set() for i in connections: edges.add(tuple(i)) neighbors=defaultdict(list) for a,b in connections: neighbors[a].append(b) neighbors[b].append(a) visited=set() count=0 def dfs(city): nonlocal count visited.add(city) for i in neighbors[city]: if(i not in visited and (i,city) not in edges): count+=1 dfs(i) elif(i not in visited): dfs(i) dfs(0) return count

[@rajasaraf6602]

50 rupee kat overacting ka