Time Complexity of Both Approaches : O(m+n) , where m = number of edges n = number of vertices We build an adjacent list of all m edges in graph which takes O(m). Each node is added to the queue and popped from the queue once, it takes O(n) to handle all nodes. Total : O(m+n)
I did this Question using DSU. Thank you so much Bhaiya, Now i start feeling Confident in Graphs. You just liked my comment, U may be awake, I want you to know that Im very very Grateful🫂
I was able to solve this question by my own after completing your Graph concepts and Questions Playlist...It helped me a lot in improving my graph concepts. Thank you so much Bhaiya😊
Thanks for the reply ❤❤ Here is my code in Java class DisjointSet{ int[] parent, rank; int n; DisjointSet(int n){ this.n = n; parent = new int[n]; rank = new int[n]; makeSet(); } public void makeSet(){ for(int i=0;irank[yRoot])parent[yRoot] = xRoot; else if(rank[yRoot]>rank[xRoot])parent[xRoot] = yRoot; else{ parent[yRoot] = xRoot; rank[xRoot]++; } } } class Solution { public boolean validPath(int n, int[][] edges, int source, int destination) { DisjointSet ds = new DisjointSet(n); for(int i=0;i
Thanks for the reply ❤ Here is my Union find code in Java class DisjointSet{ int[] parent, rank; int n; DisjointSet(int n){ this.n = n; parent = new int[n]; rank = new int[n]; makeSet(); } public void makeSet(){ for(int i=0;irank[yRoot])parent[yRoot] = xRoot; else if(rank[yRoot]>rank[xRoot])parent[xRoot] = yRoot; else{ parent[yRoot] = xRoot; rank[xRoot]++; } } } class Solution { public boolean validPath(int n, int[][] edges, int source, int destination) { DisjointSet ds = new DisjointSet(n); for(int i=0;i
In line 15 of your code for DFS in leetcode IDE, before doing the recursive call check if the node in the map is already visited. if (visited[node] === false) { // do the recursive call here, it'll reduce number of recursive calls for already visited nodes. // you can remove line 8 & 9, as you're already checking the same before the recursive call. }
This was my code: public static boolean validPath(int n, int[][] edges, int source, int destination) {
List adj = new ArrayList(); for (int i = 0; i < n; i++) { adj.add(new ArrayList()); } int[] vis = new int[n]; // creating the adjacency list. for (int[] list : edges) { int u = list[0]; int v = list[1]; adj.get(u).add(v); adj.get(v).add(u); } return dfs(source, destination, adj, n, vis); } private static boolean dfs(int node, int destination, List adj, int n, int[] vis) { vis[node] = 1;
if (node == destination) { return true; } for(Integer it : adj.get(node)) { if (vis[it] == 0 && dfs(it, destination, adj, n, vis)) { return true; } } return false; } support++ reach++
Try this - def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: paths = collections.defaultdict(lambda: list()) # build graph using adjacency list for [v1, v2] in edges: paths[v1].append(v2) paths[v2].append(v1) # apply DFS visited = [False] * n def dfs(s, d): if s == d: return True if visited[s]: return False visited[s] = True res = False for v in paths[s]: res = res or dfs(v, d) return res return dfs(source, destination)
No , even if it's a directional graph , still we will be using the visited array , consider an example where there is an edge from 3 --> 5 and another edge from 5 --> 3 , in that case the code will go from node 3 to node 5 and again from node 5 to node 3 (Because we have not marked the nodes visited), so it will visit the nodes again and again and this will be repeated and it will give you TLE/Memory LIMIT Exceeded.
Time Complexity of Both Approaches : O(m+n) ,
where m = number of edges
n = number of vertices
We build an adjacent list of all m edges in graph which takes O(m).
Each node is added to the queue and popped from the queue once, it takes O(n) to handle all nodes.
Total : O(m+n)
I used disjoint set-
class dj{
public:
vector parent;
vector size;
dj(int n){
parent.resize(n);
size.resize(n);
for(int i=0;isize[pu]){
size[pv]+=size[pu];
parent[pu]=pv;
}
else{
size[pu]+=size[pv];
parent[pv]=pu;
}
}
};
class Solution {
public:
bool validPath(int n, vector& edges, int source, int destination) {
dj d(n);
for(int i=0;i
Awesome ❤️😇
Jinhone bhaiya ka graphs and concept playlist kia hai unke liye ye question halwa hai 😂😂❤❤. Thanks a lot bhaiya ❤❤
❤️❤️🙏🙏
This channel is a GEM 💎
You are the best. I had completed your Graph concepts playlist and these Qns I can do on my own.
Solved on my own .........all because of your graph playlist ......Thank u so much from the bottom of my heart💖💖
I am so happy that we are now able to solve and think about Graph qns on our own. Thank you for sharing your experience 🙏🙏❤️❤️
I did this Question using DSU.
Thank you so much Bhaiya, Now i start feeling Confident in Graphs.
You just liked my comment, U may be awake, I want you to know that Im very very Grateful🫂
So glad to know ♥️😇
Yes I was awake. Travelling ✈️
I was able to solve this question by my own after completing your Graph concepts and Questions Playlist...It helped me a lot in improving my graph concepts. Thank you so much Bhaiya😊
Solved on my own, using Union find, all thanks to your graph playlist
So happy to see this.
Feel free to share your code here so that others can also benefit from it ❤️🙏😇
Thanks for the reply ❤❤
Here is my code in Java
class DisjointSet{
int[] parent, rank;
int n;
DisjointSet(int n){
this.n = n;
parent = new int[n];
rank = new int[n];
makeSet();
}
public void makeSet(){
for(int i=0;irank[yRoot])parent[yRoot] = xRoot;
else if(rank[yRoot]>rank[xRoot])parent[xRoot] = yRoot;
else{
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
DisjointSet ds = new DisjointSet(n);
for(int i=0;i
Thanks for the reply ❤
Here is my Union find code in Java
class DisjointSet{
int[] parent, rank;
int n;
DisjointSet(int n){
this.n = n;
parent = new int[n];
rank = new int[n];
makeSet();
}
public void makeSet(){
for(int i=0;irank[yRoot])parent[yRoot] = xRoot;
else if(rank[yRoot]>rank[xRoot])parent[xRoot] = yRoot;
else{
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
DisjointSet ds = new DisjointSet(n);
for(int i=0;i
done using 3 methods DFS,BFS,DSU
good one
Please make playlist on Graphs. And thanks for this video.
Sure.
Thank you so much 😊
bhaiya computer fundamentals jo interview mey puchi jati hai unpe bhi playlist suuru kardo ya batado kaha se kya kya aur kitna padna hai !!
"Minimums number of operation to satisfy Conditions", pe bhi vidio bna dijie
This channel is G.O.L.D
DFS line 12-13 ... idk c++ much, but vector int is like an int array??, so how are you pushing the int there?
Please start the Playlist for not only graph but also for other as well till advance
Hi Manish, i have planned to cover all topics. Soon planning. One by one
Thanks for watching ❤️❤️❤️
bhaiya daily challenge k sath sath leetcode best question ka topicwise playlist karao sirf leetcode
Soon ❤️❤️❤️
You are just awesome
bro can you make video explanation of letter combination of a phone number from leetcode
Noted.
Thanks for asking. Planning soon
Thank you , Can be done using DSU as well. dsu.findPar(src) == dsu.findPar(dest) return true else false
In line 15 of your code for DFS in leetcode IDE, before doing the recursive call check if the node in the map is already visited.
if (visited[node] === false) {
// do the recursive call here, it'll reduce number of recursive calls for already visited nodes.
// you can remove line 8 & 9, as you're already checking the same before the recursive call.
}
Indeed.
Thank you so much for pointing this out ❤️❤️❤️
Thanks dude and thats imp since it can lead to multiple waste calls leading to TLE
100th Like in this video 🤩
This was my code:
public static boolean validPath(int n, int[][] edges, int source, int destination) {
List adj = new ArrayList();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList());
}
int[] vis = new int[n];
// creating the adjacency list.
for (int[] list : edges) {
int u = list[0];
int v = list[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
return dfs(source, destination, adj, n, vis);
}
private static boolean dfs(int node, int destination, List adj, int n, int[] vis) {
vis[node] = 1;
if (node == destination) {
return true;
}
for(Integer it : adj.get(node)) {
if (vis[it] == 0 && dfs(it, destination, adj, n, vis)) {
return true;
}
}
return false;
}
support++
reach++
❤❤
done [24.12.23] ✅✅
mera TLE maar rha 30th (lat) test case par
Share your code
Try this -
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
paths = collections.defaultdict(lambda: list())
# build graph using adjacency list
for [v1, v2] in edges:
paths[v1].append(v2)
paths[v2].append(v1)
# apply DFS
visited = [False] * n
def dfs(s, d):
if s == d: return True
if visited[s]: return False
visited[s] = True
res = False
for v in paths[s]:
res = res or dfs(v, d)
return res
return dfs(source, destination)
@@codestorywithMIK class Solution {
public:
bool solve( unordered_map&adjList,int s,int d,vector&vis){
if(s==d)return 1;
if(vis[s]==1)return 0;
vis[s]=1;
for(auto ele:adjList[s]){
if(solve(adjList,ele,d,vis))return 1;
}
return 0;
}
bool validPath(int n, vector& edges, int source, int destination) {
unordered_mapadjList;
for(auto i:edges){
adjList[i[0]].push_back(i[1]);
adjList[i[1]].push_back(i[0]);
}
vectorvis(n+1,0);
return solve(adjList,source,destination,vis);
}
};
@@kumkumslab5811 same mera bhi tle de rh
We have used visted array only because it's a bidirectional graph?
No ,
even if it's a directional graph ,
still we will be using the visited array ,
consider an example where there is an edge from 3 --> 5 and another edge from 5 --> 3 ,
in that case the code will go from node 3 to node 5 and again from node 5 to node 3 (Because we have not marked the nodes visited), so it will visit the nodes again and again and this will be repeated and it will give you TLE/Memory LIMIT Exceeded.
@@tejasjhamnani7724 thanks
Thanks @tejashamnani7724 . You are correct ❤️