Clone graph | Leetcode

[@akshatjain6854]

Remembering that I used to see your videos before getting placed is another level of nostalgia 😂

[@techdose4u]

Bro I also remember you used to actively interact and ask so many questions about placement. Now I am happy that you got placed :)

[@akshatjain6854]

@@techdose4u Thank you so much brother, My resume was shortlisted because of the coding profile that I made on leetcode.And It was because of you I was able to solve 210 problems on leetcode.Worked harder for those 3 months , watched your tutorial everyday and recommended the same to all my friends. It helped a lot in my interviews To anyone who is reading this and preparing for SDE role, this channel is the best one and in fact far better than all the paid courses.He is doing a social work by uploading these amazing tutorials so guys support him as much as you can!

[@agileprogramming7463]

@@akshatjain6854 Cannot agree more. Btw can you please tell how you got shortlisted based on your Leetcode profile ?

[@akshatjain6854]

@@agileprogramming7463 I had put my leetcode profile link in resume.I think that helped because before putting this I wasn't getting shortlisted for interviews

[@spetsnaz_2]

@@akshatjain6854 Which company did you get cracked bro ?

[@AstonishingStudios]

In the cloneGraph function, you could remove all lines below the creation of "copy", excluding the "return copy;" line, and precede the "return copy;" with "DFS(node, copy, visited);" so you don't have to write a for loop twice.

[@aryamarda1643]

You teach at a very different level, clear to understand, explained deeply.and code easy to understand

[@techdose4u]

Thanks

[@bostonlights2749]

Commenting for the YT algorithm so that this channel gets famous. Awesome stuff bro

[@techdose4u]

Thanks :)

[@abhishekjaiswal6492]

i think time complexity should be O(V+E) same as dfs because no extra loop or recursion is there .

[@shresthmishra9329]

When I click on any of your video, I know for sure that I won't forget the concept. Thank you for such great videos and clear/precised explanations. Miss your frequent videos though.

[@techdose4u]

Yep....I am at home now. I will start upload from tommorow :) Stay tuned!

[@muskangupta5873]

After Watching it twice I got the logic thank you very much bro!!

[@techdose4u]

Great

[@ayushanand1032]

I wonder.... why I always get confused by the way you explain any problem!!!!😕😕

[@sandeepsaluru6587]

Solution in python using dfs first to make adjacency list, then copying it using new nodes. I think this will be useful. Leetcode accepted submission in python from collections import defaultdict # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] class Solution: def cloneGraph(self, node: 'Node') -> 'Node': adj = defaultdict(list) visited =[False]*101 queue = [] if node is None: print(node) return if len(node.neighbors) == 0: return Node(node.val) self.dfs(node, visited, adj) ans = [] for i in list(adj.keys()): ans.append(adj[i]) new_nodes = defaultdict(list) for key in list(adj.keys()): new_nodes[key].append(Node(val = key)) for key in list(adj.keys()): nei = adj[key] if len(adj[key]) == 0: continue else: for nei in adj[key]: new_nodes[key][0].neighbors.append(new_nodes[nei][0]) return new_nodes[1][0] def dfs(self, node, visited, adj): visited[node.val] = True if len(node.neighbors) == 0: return for neighbour in node.neighbors: if visited[neighbour.val] == False: adj[node.val].append(neighbour.val) self.dfs(neighbour, visited, adj) else: adj[node.val].append(neighbour.val) return

[@arnavkarforma3015]

Just in case if anyone is looking for the same dfs based solution in java class Solution { public HashMap map = new HashMap(); public Node cloneGraph(Node node) { return clone(node); } public Node clone(Node node) { if (node == null) return null; if (map.containsKey(node.val)) return map.get(node.val); Node newNode = new Node(node.val, new ArrayList()); map.put(newNode.val, newNode); for (Node neighbor : node.neighbors) newNode.neighbors.add(clone(neighbor)); return newNode; } }

[@techdose4u]

👍

[@jaydave2500]

The first for loop in main will not be required we can directly call dfs cause the graph is connected....

[@techdose4u]

Yea. Only if it's connected.

[@damanpreetsingh6530]

Best Explaination

[@techdose4u]

Thanks :)

[@shobhitkumar6820]

why can' t we use visited[node->val] for the visited array??

[@rohitsoni9611]

Nice Explanation Simple Java Code: class Solution { Node[] visited = new Node[101];//keep a track of visited nodes public Node cloneGraph(Node node) { return dfs(node); } public Node dfs(Node root){ if(root==null) return null; if(visited[root.val]==null) { Node copy = new Node(root.val); visited[root.val] = copy; for(int i=0;i

[@techdose4u]

👍🏼

[@nikhilchandna4851]

Shouldn't the time complexity be O(V+E) instead of O(VE) , since we are keeping track of visited nodes??

[@voldemort576]

Yes i also think so! but when graph is complete connected E = V*(V-1)

[@rohankumarshah5679]

very wonderful tutorial, but you code is giving run time error in interview bit while submitting but it works fine while testing

[@harshtyagi700]

Great Explaination

[@techdose4u]

Thanks 😊

[@bhaskersaiteja9531]

If possible explain the time complexity again please

[@garimaagrawal5937]

Sir will you make videos on leetcode july challenge also? Your june challenge series really helped a lot 😊

[@techdose4u]

I will make only selected questions

[@paragroy5359]

Great content, Keep on making such videos.

[@mahipalsingh-yo4jt]

very good explanation......... Thanks ...

[@techdose4u]

Welcome :)

[@caminante4222]

you have the best explanations

[@techdose4u]

Thanks

[@rahulsrivastava9710]

why can't we compare node->val as simple visited array ?

[@setYourHandleHttp404]

Thanks for your excellent explanations! BFS and HashMap weren't easier?

[@kunalagrawal2050]

what was the time complexity

[@kunalsoni7681]

Sir Really your explanation style is brilliant 😊☺️.. you always explain brute force approach firstly then you will go to optimise approach so that everyone can understand deeply 😇.. thank you sir..

[@lipishah474]

Thank you so much for such a nice explanation sir ☺️

[@techdose4u]

Welcome :)

[@spetsnaz_2]

[PYTHON SOLUTION] 1 liner I found a very simple way to solve this question in just 1 line using Python 😂 return deepcopy(node)

[@techdose4u]

Can't explain like this in interview 😅

[@spetsnaz_2]

@@techdose4u true, but these kind of solutions are just for fun. Otherwise the interviewer will kick me 😂

[@manvisingh307]

Awesome explanation ! which software did you use for making these videos?

[@VenkatIyer]

Amazing explanation. Just a quick question, on the code where is the backtracking happening? Is it because the (node->neighbors) vector is already flooded with the newly made nodes?

[@agileprogramming7463]

TECH DOSE is back!!!!

[@techdose4u]

Yep 😁

[@RakeshKumar-he6ek]

Great!

[@Arjun69]

LEGEND.

[@techdose4u]

😄

[@mystryb345]

Bro posssible plz cover median of Two sorted array

[@techdose4u]

I will try when I start that topic

[@saikumartadi8494]

Sir. Isn't the time complexity equal t O(E+V) which for a complete graph is O(E) .we are basically using DFS here right? and the time complexity should be equal to that if DFS right?

[@alokesh985]

Yep, it is linear time

[@SiddheshKukade]

thanks

[@crimsoncad3230]

Bro can you make a Telegram discussion group? It'll be helpful. And if you are busy then someone else from this group can help in solving doubts.

[@techdose4u]

Soon bro soon

[@techdose4u]

Made the channel and group

[@ArpitDhamija]

@@techdose4u link?

[@ellis-pr7hh]

YOU DONT NEED TO ITERATE THROUGH THE FIRST NODE NEIGBORS CAUSE THERE ARE NOT DISCONNECTED COMPONENTS..CHECK THE BELOW CODE void dfs(Node* curr, Node* node, vector &vis){ vis[node->val] = node; for(auto i: curr->neighbors){ if(vis[i->val] == NULL){ Node* newnode = new Node(i->val); (node->neighbors).push_back(newnode); dfs(i, newnode, vis); } else{ (node->neighbors).push_back(vis[i->val]); } } } Node* cloneGraph(Node* node) { if(node == NULL) return NULL; vector vis(1000, NULL); Node* newnode = new Node(node->val); dfs(node, newnode, vis); return newnode; }

[@sahilarora1794]

Excessive Simple, Just 4 Lines. Cpp. class Solution { public: Node* cloneGraph(Node* node) { if(!node) return nullptr; unordered_map t; return helper(node, t); } Node* helper(Node* node, unordered_map& t){ if(t.find(node)!=t.end()) return t[node]; Node* cur = new Node(node->val); t[node] = cur; for(int i = 0;i < node->neighbors.size(); ++i){ cur->neighbors.push_back(helper(node->neighbors[i], t)); } return cur; } };

[@arjunm8431]

nice bro short lines of code

[@letsdoeverythinginoneweek9398]

this question implementation is hard

[@paraskumar693]

tc is v+e

[@spetsnaz_2]

Code link : techdose.co.in/clone-graph/

[@amitavamozumder73]

if you use a headphone you can hear him breathe in the mic. :P

[@HariKrishna-cy3ps]

Your content is so good.

[@techdose4u]

Thanks :)

[@AlanSchooll]

class Solution { vector visited; void depthFirstSearch(Node *node, Node *newNode) { for (int i = 0; i < node->neighbors.size(); i++) { if (visited[node->neighbors[i]->val - 1] == NULL) { Node *newNode2 = new Node(node->neighbors[i]->val); visited[node->neighbors[i]->val - 1] = newNode2; newNode->neighbors.push_back(newNode2); depthFirstSearch(node->neighbors[i], newNode2); } else { newNode->neighbors.push_back(visited[node->neighbors[i]->val - 1]); } } } public: Node* cloneGraph(Node *node) { if (node == NULL) return NULL; vector temp(100, NULL); visited = temp; Node *copyNode = new Node(node->val); visited[node->val - 1] = copyNode; depthFirstSearch(node, copyNode); return copyNode; } };

[@shreshthsingh7744]

""" PYTHON CODE # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """ class Solution: def cloneGraph(self, node: 'Node') -> 'Node': visited = [None]*1000 def connect(node): if node==None: return None if visited[node.val-1]!=None: return visited[node.val-1]=Node(node.val,None) for nbr in node.neighbors: connect(nbr) newNbrs = [] for nbr in node.neighbors: newNbrs.append(visited[nbr.val-1]) visited[node.val-1].neighbors = newNbrs connect(node) return (visited[0])

[@alexsparrow8614]

OMG ........ Where is today leet code solution ?

[@techdose4u]

It was so simple that I dint upload it. Please follow my community post announcement.

[@rks3522]

10:40

[@parthkumartilva6611]

Node* vis[101]={NULL}; Node* cloneGraph(Node* node) { if(node==NULL) return node; Node* nn=new Node(node->val); vis[node->val]=nn; for(auto it:node->neighbors){ if(vis[it->val]==NULL){ Node* adj=cloneGraph(it); nn->neighbors.push_back(adj); } else{ nn->neighbors.push_back(vis[it->val]); } } return nn; }

[@ashishupadhyay6881]

/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ unordered_mapmp; UndirectedGraphNode *Solution::cloneGraph(UndirectedGraphNode *node) { if(!node) return NULL; if(mp.find(node)==mp.end()){ mp[node] = new UndirectedGraphNode(node->label); for(auto it: node->neighbors) mp[node]->neighbors.push_back(cloneGraph(it)); } return mp[node]; }

[@ellis-pr7hh]

could you explain plz a lil bit

[@venkateshthirunagiri85]

Bro start from what is Graph & it's Applications & implementation Don't jump to direct problems 📈📈📈

[@techdose4u]

I had already started. I am covering graph for interviews. I cannot cover what is graph 😅

[@shreshthsingh7744]

@@techdose4u For this they shud refer Jenny.

[@rithikrk3695]

approach was good but code explanation was not proper.

[@joydeeprony89]

from 11:06 its started getting confusing.