Clone Graph | Leetcode - 133 | Google, Facebook, Amazon | DFS+BFS | Explanation ➕ Live Coding🧑🏻‍💻

[@anuppatankar4294]

Graph was very tough for me but because of your graph concepts playlist today I can solve most of the graph questions easily. Thanks a Lot 😊

[@codestorywithMIK]

You made my day ❤️❤️❤️

[@shivanshchauhan52]

@@codestorywithMIK Keep going this channel future is very bright !!!

[@codestorywithMIK]

Thank you so much Shivansh ❤️❤️❤️

[@kumkumslab5811]

prooved @@shivanshchauhan52

[@codestorywithMIK]

The most detailed and deep dived explanation to this problem you will ever find. Hope you will like it. Please find all the code below : //Approach-1 (DFS) Using vector as map //Approach-2 (DFS) (Using unordered_map) //Approach-3 (BFS) Using vector as map //Approach-4 (BFS) (Using unordered_map) Link : github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp

[@souravjoshi2293]

The best one bro. I am speechless

[@oqant0424]

Yaar bhaiya kya padhaya hai aapne ...........dil khush kar diya

[@codestorywithMIK]

Thank you 🙏❤️😇

[@JJ-tp2dd]

Outstanding bhai! You prove every time why you are the undisputed graph king 👑💙💙

[@codestorywithMIK]

Thank you so much JJ

[@souravjoshi2293]

speechless with this masterpiece

[@souravjoshi2293]

16:59 ---> That's one of the reasons I come to your channel. I am always sure that I will understand more from your explanations.

[@nk-fs8bj]

Awesome after listing story of 20 minutes write code by own🥳

[@r.beditz3674]

Never regret watching your explanation videos.❤ Thanks again sir. Here are the Java implementations of your BFS and DFS approaches -: BFS CODE : class Solution { Map map; public Node cloneGraph(Node node) { map = new HashMap(); if(node == null) return null; Node clone = new Node(node.val); map.put(node, clone); Queue q = new ArrayDeque(); q.add(node); while(!q.isEmpty()){ Node curr = q.poll(); Node currClone = map.get(curr); for(Node n : curr.neighbors){ if(!map.containsKey(n)){ Node c = new Node(n.val); map.put(n, c); currClone.neighbors.add(c); q.add(n); } else currClone.neighbors.add(map.get(n)); } } return clone; } } ---------------------------------------------------------------------------------------------------- DFS CODE : class Solution { Map map; public Node cloneGraph(Node node) { map = new HashMap(); if(node == null) return null; Node clone = new Node(node.val); map.put(node, clone); dfs(node, clone); return clone; } private void dfs(Node node, Node clone){ for(Node n : node.neighbors){ if(!map.containsKey(n)){ Node curr = new Node(n.val); map.put(n, curr); clone.neighbors.add(curr); dfs(n, curr); } else clone.neighbors.add(map.get(n)); } } }

[@codestorywithMIK]

Thank you so so much Means a lot to me ❤️

[@HarshSharma-zz9di]

Was able to do today's question without any help, but still here just to like the video. Amazing channel and well structured videos!

[@k-CE-OmkarPathak]

Awesome !! Worth watching 41mins

[@codestorywithMIK]

Thank you so much for watching 😇❤️🙏

[@gauravbanerjee2898]

Solved today's GFG POTD after watching this video thank you so much bhaiya ❤❤

[@codestorywithMIK]

Awesome ❤️❤️

[@ShivamMishra-fo1wx]

Great Explanation Makes the question very easy to understand and not only graph u make easy dp also

[@iamnoob7593]

Thank you , Amazing explanation.

[@level_up.1908]

bhai kyu padhate hon itna badhiya 😍

[@codestorywithMIK]

Means a lot ❤️😇

[@fshimcds]

ThankU for best Explanation

[@shivkumar-og4ow]

thanks a lot, bhaiya, nice explanations, are easy to understand.

[@souravjoshi2293]

The K.I.N.G of Graphs

[@JJ-tp2dd]

so true!

[@rahularyan9808]

Really great explanation

[@udayshankar-e6v]

Ye channel bahut aage jane vale h.. bahut bawal samjhata h ye bhai 😍bhai bs bata do kon sa aap use karte ho drawing ke liye .. main bhi install kar lunga..interview me bada proplem hota h diagram vagairh bana ke show karne me

[@codestorywithMIK]

Hi there I use default notes app ❤️🙏 Thank you ☺️

[@tutuimam3381]

Thanks a lot

[@souvickmaity4867]

Shi Haai bhai

[@gui-codes]

A message to new comers to this channel - "Graph is Hard until you watch codestorywithMIK"

[@aryanvashishtha0001]

i love you bro

[@vishalgautam-f6v]

bro u are great at explaining things but u should change ur channel name to a short and simple name, so that we can also recommend ur channel to others as ur current name is slightly difficult to remember

[@codestorywithMIK]

I really appreciate your suggestion ❤️❤️❤️ I will plan to change it to CSM (Code Story With MIK). Right now, my Instagram, linkedIn and , Facebook all have this name and hence might take time to migrate. Thank you so much for your precious suggestions and watching my videos ❤️❤️❤️

[@ankitraj4179]

Java Solution /* // Definition for a Node. class Node { public int val; public List neighbors; public Node() { val = 0; neighbors = new ArrayList(); } public Node(int _val) { val = _val; neighbors = new ArrayList(); } public Node(int _val, ArrayList _neighbors) { val = _val; neighbors = _neighbors; } } */ class Solution { public Node cloneGraph(Node node) { if(node == null) return node ; Node clone = new Node(node.val) ; HashMap map = new HashMap() ; map.put(node,clone) ; DFS(node,clone,map) ; return clone ; } public static void DFS(Node org , Node clone , HashMap map){ for(Node neigh : org.neighbors){ if(!map.containsKey(neigh)){ Node tempNode = new Node(neigh.val) ; clone.neighbors.add(tempNode) ; map.put(neigh,tempNode) ; DFS(neigh,tempNode,map) ; } else{ clone.neighbors.add(map.get(neigh)); } } } }

[@ankitraj4179]

do like if it helped.

[@YashSinghal]

github link in the description for this problem has a typo its a space instead of underscore so %20 instead of _

[@codestorywithMIK]

Thank you so much Yash. Corrected now. github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp

[@jyotishmoydeka6804]

Bhaiya it's showing your github page is not available.. and btw thank you for wonderfull explainantion..

[@codestorywithMIK]

Sorry for the typo. Link corrected. github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp

[@abhiverma5135]

why you wrote map.clear() at the beginning of the function ? whereas we hadn't put any value in the map we just declared it globally? BTW great content ❤✌✌

[@codestorywithMIK]

Hi abhi, Thanks a lot for your appreciation. Actually multiple calls for the function is made. So we don’t want stale entries in the map to be there when a new call is made to the function. But most of the time , even if you don’t clear it, the solution works. But it’s a good practice to do that.

[@bhartendupant8859]

❤

[@satvrii]

❤❤❤❤

[@codestorywithMIK]

❤️🙏 Means a lot 😇

[@badamadevi9497]

Sir java ka code bhi explain krr

[@riyakansal3312]

Error is coming while opening ur github:(

[@codestorywithMIK]

Link corrected. Can you try again please github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Clone%20Graph.cpp

[@IshanGuleria-l6b]

iska iterative dfs ka solution h kisi k pass to please send

[@vinitsinghengineer]

unordered_map mp; void dfs(Node* node){ Node* temp = new Node(node->val); mp[node] = temp; for(auto it : node->neighbors){ if(mp.find(it) != mp.end()) temp->neighbors.push_back(mp[it]); else { dfs(it); temp->neighbors.push_back(mp[it]); } } } Node* cloneGraph(Node* node) { if(!node) return NULL; dfs(node); return mp[node]; }

[@akshayzade9761]

Thanks Mike for efforts :) Please find below Java Code - class Solution { Map map = new HashMap(); public Node cloneGraph(Node node) { if(node == null){ return null; } Node clone_node = new Node(node.val); map.put(node, clone_node); dfs_traversal(node, clone_node); return clone_node; } void dfs_traversal(Node node, Node clone_node){ for(Node n : node.neighbors){ if(!map.containsKey(n)){ Node clone = new Node(n.val); map.put(n, clone); clone_node.neighbors.add(clone); dfs_traversal(n, clone); } else{ clone_node.neighbors.add(map.get(n)); } } } }

[@JJ-tp2dd]

Why is my comment getting removed?😮

[@JJ-tp2dd]

tried several times to paste the Java code but it is getting removed every time automatically 😥😥

[@codestorywithMIK]

Hi JJ Can you try again. I am also not sure why this is happening

[@souravjoshi2293]

Was waiting for your java code bro

[@JJ-tp2dd]

@@codestorywithMIK @asimzohr2293 added, hoping it does not get removed

[@JJ-tp2dd]

@@codestorywithMIK it got removed again it seems 😐

[@kartikkk4583]

Hogya bhai ye, recursion + map, time laga thoda dimag lagane me, @mik bhai aapne competetive programming ki hai kya : unordered_map m; Node* cloneGraph(Node* node) { if(!node)return node; Node* root= new Node(node->val); vector v; m[node]=root; for( auto x : node->neighbors){ if(m.find(x)==m.end()){ v.push_back(cloneGraph(x)); } else{ v.push_back(m[x]); } } root->neighbors=v; return root; }

[@codestorywithMIK]

Hi Kartik, No, i have not done much in Competitive Coding. But would love to try

[@abcd76820]

class Solution{ Node cloneGraph(Node node){ Node temp = new Node(node.val); //ab clone krna h recursively iske neighbours ko // saath me ek map bna lete hain taaki koi node bn gya h // to dubara nahi bnega //map ek purana node usk corresponding new node jo //hmne bnaya Map map = new HashMap(); map.put(node,temp); DFS(node,temp,map); return temp; } void DFS(Node node,Node temp,Map map) { //original node k neighbours dhund kr clone krte jaao for(Node neigh : node.neighbors) { // ab do case ya to clone hua hoga ya to nai if(!map.containsKey(neigh)) { Node cloneNeigh = new Node(neigh.val); map.put(neigh,cloneNeigh); temp.neighbors.add(cloneNeigh); DFS(neigh,cloneNeigh,map); } else { temp.neighbors.add(map.get(neigh)); } } } }

[@sarthakgudwani4608]

Java Implementation class Solution { HashMap mp = new HashMap(); void DFS(Node node, Node clone_node) { for (Node n : node.neighbors) { if (!mp.containsKey(n)) { Node clone = new Node(n.val); mp.put(n, clone); clone_node.neighbors.add(clone); DFS(n, clone); } else { clone_node.neighbors.add(mp.get(n)); } } } Node cloneGraph(Node node) { if (node == null) { return null; } mp.clear(); Node clone_node = new Node(node.val); mp.put(node, clone_node); DFS(node, clone_node); return clone_node; } }

[@dayashankarlakhotia4943]

class Solution { Node cloneGraph(Node node){ Node st=node; HashSetvis=new HashSet(); HashMapmpp=new HashMap(); dfs(st,vis,mpp); addEdges(mpp); return mpp.get(st); } public static void addEdges(HashMapmpp){ for(Map.Entery e:mpp.entrySet()){ Node u=(Node)e.getKey(); mpp.get(e.getKey()).neighbors.add(u); } } public void dfs(Node st,HashSetvis,HashMapmpp){ vis.add(st); Node copyNode=new Node(st.val); mpp.put(st,copyNode); for(Node v:st.neighbors){ if(!vis.contains(v)) dfs(v,vis,mpp); } } } 🎉❤