@@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 I had put my leetcode profile link in resume.I think that helped because before putting this I wasn't getting shortlisted for interviews
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.
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.
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])
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)
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..
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; } }
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?
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?
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]); } } }
""" 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])
Remembering that I used to see your videos before getting placed is another level of nostalgia 😂
Bro I also remember you used to actively interact and ask so many questions about placement. Now I am happy that you got placed :)
@@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!
@@akshatjain6854 Cannot agree more.
Btw can you please tell how you got shortlisted based on your Leetcode profile ?
@@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
@@akshatjain6854 Which company did you get cracked bro ?
Commenting for the YT algorithm so that this channel gets famous.
Awesome stuff bro
Thanks :)
You teach at a very different level, clear to understand, explained deeply.and code easy to understand
Thanks
i think time complexity should be O(V+E) same as dfs
because no extra loop or recursion is there .
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.
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.
Yep....I am at home now. I will start upload from tommorow :) Stay tuned!
Best Explaination
Thanks :)
Great content,
Keep on making such videos.
After Watching it twice I got the logic thank you very much bro!!
Great
very good explanation......... Thanks ...
Welcome :)
I wonder.... why I always get confused by the way you explain any problem!!!!😕😕
Great Explaination
Thanks 😊
The first for loop in main will not be required we can directly call dfs cause the graph is connected....
Yea. Only if it's connected.
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
you have the best explanations
Thanks
TECH DOSE is back!!!!
Yep 😁
Thank you so much for such a nice explanation sir ☺️
Welcome :)
Shouldn't the time complexity be O(V+E) instead of O(VE) , since we are keeping track of visited nodes??
Yes i also think so! but when graph is complete connected E = V*(V-1)
why can' t we use visited[node->val] for the visited array??
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..
If possible explain the time complexity again please
Great!
very wonderful tutorial,
but you code is giving run time error in interview bit while submitting but it works fine while testing
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
👍🏼
LEGEND.
😄
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;
}
}
👍
why can't we compare node->val as simple visited array ?
Sir will you make videos on leetcode july challenge also?
Your june challenge series really helped a lot 😊
I will make only selected questions
Code link : techdose.co.in/clone-graph/
[PYTHON SOLUTION] 1 liner
I found a very simple way to solve this question in just 1 line using Python 😂
return deepcopy(node)
Can't explain like this in interview 😅
@@techdose4u true, but these kind of solutions are just for fun.
Otherwise the interviewer will kick me 😂
thanks
Thanks for your excellent explanations! BFS and HashMap weren't easier?
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.
Soon bro soon
Made the channel and group
@@techdose4u link?
what was the time complexity
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?
Awesome explanation ! which software did you use for making these videos?
Bro posssible plz cover median of Two sorted array
I will try when I start that topic
this question implementation is hard
Your content is so good.
Thanks :)
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?
Yep, it is linear time
if you use a headphone you can hear him breathe in the mic. :P
tc is v+e
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;
}
10:40
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; } };
nice bro short lines of code
OMG ........ Where is today leet code solution ?
It was so simple that I dint upload it. Please follow my community post announcement.
"""
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])
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;
}
};
Bro start from what is Graph & it's Applications & implementation
Don't jump to direct problems 📈📈📈
I had already started. I am covering graph for interviews. I cannot cover what is graph 😅
@@techdose4u For this they shud refer Jenny.
approach was good but code explanation was not proper.
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;
}
/**
* 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];
}
could you explain plz a lil bit
from 11:06 its started getting confusing.