Reorder Routes to Make All Paths Lead to the City Zero | Leetcode - 1466 | META | DFS | Live Coding

[@arjunsolanki752]

Great explanation exists on KZbin❤

[@codestorywithMIK]

Thanks a lot Arjun

[@souravjoshi2293]

true bhai

[@iamnoob7593]

Mik , This is a fabulous explanation , Again a tough problem.

[@molyoxide8358]

I usually don't watch videos more than 15 mins but yours is the only one where I watch without any limits.

[@codestorywithMIK]

It means a lot ❤️

[@molyoxide8358]

@@codestorywithMIK TYSM

[@anuppatankar4294]

After watching your explanation, I coded it myself👍🏻

[@codestorywithMIK]

We all are growing together. That’s all i want ❤️💪

[@anuppatankar4294]

@@codestorywithMIK Yes bro 🤝🏻🔥

[@ayush_24]

10:45 kaash zindegi main bhi aise he pata chal jaata 🥲🥲

[@souravjoshi2293]

Bhai, you are an example of perfection

[@souradeep.23]

Thank you💥. Can you upload a solution for this based on DSU please ?

[@codestorywithMIK]

Let me think about DSU for this. I like that we are now curious about DSU. Thanks for asking. Will definitely check DSU

[@vaibhavgupta973]

thank you ! this was a really interested question . learned something new from this problem today !!

[@codestorywithMIK]

Indeed ❤️👍🏻

[@AnjuGupta-sz1uk]

Awesome explanation 😀

[@shikharpandya4927]

great explaination

[@ankitagrahari7453]

Genius🙌

[@doingit621]

plz keep posting daily

[@codestorywithMIK]

Sure thing 👍🏻💪

[@doingit621]

@@codestorywithMIK can u share ur linkedin?

[@xiaoshen194]

Ramzan Mubarak Bhai. Thank u for ur efforts 🙏

[@codestorywithMIK]

Ramzan Mubarak ❤️

[@rahulmaurya6451]

Great Explanation as always ❤

[@codestorywithMIK]

Thanks a lot Rahul ❤️

[@tutuimam3381]

Thanks a lot🌹

[@prudhvirajmacherla9854]

Hero

[@thegreekgoat98]

Saw first 10 minutes of this video, and able to code myself. But I have a doubt, is it feasible to have this much of time and memory (one that you see after a submission in leetcode)??

[@codestorywithMIK]

Comments like these make me so happy

[@thegreekgoat98]

@@codestorywithMIK is it feasible to have this much of time and memory (one that you see after a submission in leetcode)??

[@fashionvella730]

its time complexity is same as normal DFS nothing more than that O(V+E)

[@ShivamGupta-cx3hy]

thank you''' so much

[@rev_krakken70]

What a nice explanation, however this intuition looks simple but kind of hard to come by. How did you come up with this?

[@sarveshjoshi6913]

same Qn in microsoft OA today😥

[@Ramneet04]

What if there is a edge between 2 and 5 how will it work?? How we can have parent as it will become a cycle

[@gaurimandot5788]

C++ code class Solution { private: void dfs(unordered_map &adjList,int node,vector&vis,int &flip){ vis[node]=true; for(auto i:adjList[node]){ if(vis[i.first]==false){ if(i.second==1){ flip++; } dfs(adjList,i.first,vis,flip); } } } public: int minReorder(int n, vector& connections) { //Hum routes ko bidirectional bana rahe hai //1 weight for asli route //0 weight for nakli route //dfs traversal karenge //agar u->v hum asli route se jaa paa rahe hai matlab v->u hume nakli route se aana padega //Hence uss route ko flip karna hoga unordered_map adjList; for(int i=0;i

[@prajwalshaw9217]

Sir is the tc of this question..O(v+2e)...and sc is O(1)..?

[@alphagaming5432]

linked list series bhi lao basic se boht basic se

[@codestorywithMIK]

Noted . Currently there is a linked list playlist for Qns. I will create another one for basics and from beginning for LinkedList

[@aakshatmalhotra8088]

for traversal in undirected graph we only need parent not the visited vector?? Is this right (or is it only true for tree)?

[@iamnoob7593]

parent is for tree only.

[@nish0798]

class pair { int dest; int typeofedge; public pair(int dest, int typeofedge) { this.typeofedge = typeofedge; this.dest = dest; } } class Solution { static int count = 0; public int minReorder(int n, int[][] connections) { boolean[] vis = new boolean[n]; ArrayList gra = new ArrayList(); for (int i = 0; i < n; i++) { gra.add(new ArrayList()); } for (int[] c : connections) { int src = c[0]; int dest = c[1]; gra.get(src).add(new pair(dest, 1)); // real edge gra.get(dest).add(new pair(src, 0)); // fake edge we created } for (int i = 0; i < n; i++) { if (vis[i] == false) { dfs(gra, i, vis); } } return count; } public void dfs(ArrayList gra, int i, boolean[] vis) { vis[i] = true; for (pair nbr : gra.get(i)) { int dest = nbr.dest; int type = nbr.typeofedge; if (vis[dest]==false) { if (type == 1) { count++; } dfs(gra, dest, vis); } } } } @codestorywithMIK bro ye code maine likha after watching your video but ye errror de raha hai please tell what is issue please reply

[@manimanohar_001]

Again first view today.

[@alphagaming5432]

i was first

[@manimanohar_001]

@@alphagaming5432 i think you missed it

[@alphagaming5432]

@@manimanohar_001 no way

[@manimanohar_001]

@@alphagaming5432 don't bother a lot Buddy

[@chiragahuja4727]

god or what you are .. damn

[@codestorywithMIK]

🙏🙏❤️😇

[@kanhaiyasulay8809]

There was no need to check for the parent

[@abhiverma5135]

27:31 why you put & after auto keyword inside for loop what it'll do??

[@codestorywithMIK]

Hi abhi, Putting an “&” helps to avoid creation of extra copy of any variables. It’s called as “reference” You can refer to this link to get to know more about this : stackoverflow.com/questions/12728794/why-should-i-use-reference-variables-at-all

[@abhiverma5135]

@@codestorywithMIK okay so you mean the &vec we are using in loop is referring to the same location where actually values are stored in the memory... Right?

[@codestorywithMIK]

Exactly abhi. It helps to save time (because no copy is created) . But be cautious because, if you change vec, it will change original value.

[@abhiverma5135]

@@codestorywithMIK okay thank you so much😄😄

[@ALOKKUMAR-sd6bn]

this solution will not work for test case [[0,1],[1,2],[3,2],[3,5],[5,4],[0,4]] this test case is not present on leetcode but it will not work for this . problem is: we blindly increasing count+1 whenever we finding the check==1 but there will be possibility that we will reach to end city by another path , that thing is missing here. bhaiya , am i correct?

[@035-harshitsingh7]

bhaiya jb bhi minimum path se related ho to to bfs ke baare me sochne bola tha yha dfs se kyun kr rhe hain hm?? BFS se bhi to kr skte hain na

[@codestorywithMIK]

Yes you can solve it using BFS also. And must solve it first by BFS

[@codestorywithMIK]

Wow. Thanks a lot for sharing ❤️❤️

[@shivamsharma-oi3gn]

Why It is giving TLE for this code : class Solution { public: void DFS(int node, int parent, unordered_map adj, int &ans){ for(auto i : adj[node]){ int vertex = i.first; int check = i.second; if(vertex != parent){ if(check == 1) ans++; DFS(vertex, node, adj, ans); } } } int minReorder(int n, vector& connections) { unordered_map adj; for(auto i : connections){ int u = i[0]; int v = i[1]; adj[u].push_back({v, 1}); adj[v].push_back({u, 0}); } int count = 0; DFS(0, -1, adj, count); return count; } };

[@thegreekgoat98]

is it feasible to have this much of time and memory (one that you see after a submission in leetcode)?

[@codestorywithMIK]

It is fine for a problem like this. Because if you notice we are doing DFS only which is the ultimate solution since you have to travers the graph anyways. And for this problem, I believe there is no way to solve this without introducing extra edge and storing pair value in adjacency list. But I’ll explore more possibilities for this

[@thegreekgoat98]

@@codestorywithMIK Got it. thanks for replying.

[@udaykumarchetla6205]

Bro u hv leetcode premium?

[@codestorywithMIK]

No Uday.

[@Whirlwind03]

What an explanation brotha nailed it. // Java Code class Solution { // here type if 1 indicates that its an original edge that is given in connections array. // type if 0 indicates that its not an original edge and created manually to connect the graph. public class Edge{ int nbr; int type; public Edge(int nbr,int type){ this.nbr = nbr; this.type = type; } } private ArrayList[] graph; private int result; public void dfs(int src,int parent){ for(Edge edge:this.graph[src]){ int nbr = edge.nbr; int type = edge.type; if(nbr != parent){ if(type == 1){ this.result+=1; } dfs(nbr,src); } } } public int minReorder(int n, int[][] connections) { this.graph = new ArrayList[n]; this.result = 0; for(int i=0;i