THOSE WHO ARE WORDERING WHY IT IS O(N) + O(2E) NOT O(N*2E) For each node, the while loop runs multiple times based on the number of edges connected to that node. Here's how it works: In the first iteration, the loop runs for e1 edges, plus one extra operation for pushing and popping the node. In the second iteration, it runs for e2 edges, plus one extra operation for pushing and popping, and so on. Thus, the total time complexity is the sum of all iterations: (e1 + e2 + ... + en) + (1 + 1 + ... n times). The sum of all the edges connected to each node is equal to the total number of edges, which is 2E (since each edge is counted twice in an undirected graph). Adding the n push/pop operations gives the final complexity: O(V + 2E) because e1 + e2 + ... + en = 2E. So, the overall complexity is O(V + 2E), which simplifies to O(V + E).
Was searching for this thanks ... Just to summerize ... the inner for loop runs in O(2E) in total and not for each iteration of while so its O(V) + o(2E)
If u r confused about time complexity part, then see the following dry run of the while loop of the qs. he has solved.. This is how nodes are connected(assuming undirected graph) : 0 -> 1 ,2, 3 1 -> 0 2 -> 0, 4 3 -> 0 4 -> 2 So, total no. of edges = E = 4 For first while loop , node = 0, edges = 3 Now, before going to the for loop part, u see a constant time operation O(1) --> q.pop( ) This step will be executed every time we enter into while loop. So, for first while loop how many times for loop will execute ?? It will be equal to the no. of edges , here it will be 3. Therefore, total = ( 1 + 3 ) Similarly for all other nodes, this is how it will look : ( 1 + 3 ) + ( 1 + 1 ) + ( 1 + 2 ) + ( 1 + 1 ) + ( 1 + 1 ) = 13 = O ( V + 2 * E ) = O ( 5 + 2 * 4 )
but at the worst case it will be O(n^2) right? since a complete graph have all the vertex with (n-1) edges. which will lead [(1+(n-1))=n] at each while and for loop. since after n times it will become n square. Please confirm this. BTW thanks for the explaination
Hey Striver! Thank you for creating outstanding content and helping people interested in coding problems worldwide! Please don’t stress yourself out, take a break after this one. It’s not easy to work full time and dedicate time for this.
Are you going to teach leetcode questions just like you did in DP series? It would be very helpful if you can teach commonly asked good questions covering different graph patterns and not just the basic ones.
after seeing your post on LinkedIn that you are launching graph series 2.0 i used to see your TH-cam playlist daily now I am very happy thank you very much 💗
Understood each and every word♥. Kudos to your hard work and dedication, you are the motivation behind a lot of people. Your hardwork inspires a lot of people to work hard. Thankyou for providing such a beautiful graph series keep posting such content ♥, we all need this.
Thanks a lot stiver for putting all these playlists out. i can't imagine getting a job if you were not on youtube. i have a little doubt that in "bfsOfGraph" function the syntax of adj[ ] should be this "Vector> adj [ ]" but it is "vector adj[ ]" instead and this is a 1D vector not a vector of vector.
@@prachi1112 We are storing vector in array index, i.e array of vectors. Every node of array denotes an array . Eg -> if we write int arr[] , here data type is int , so it is array of integers, but if we write vector arr[] , here data type is vector , so it is array of vector
Time complexity of BFS may be different depending upon representation of graph. Adjacency List: O(V+E) Adjacency Matrix: O(V^2) where V=no of vertex and E = no of edges
00:01 Breadth-First Search (BFS) is a traversal technique in graphs. 02:16 Breadth-first search (BFS) traversal of the graph 04:25 Breadth-First Search (BFS) is a traversal technique in graphs. 06:37 Breadth-First Search (BFS) is a traversal technique in graphs. 08:54 Performing BFS traversal on a graph using adjacency list representation 11:35 BFS traversal of graph 14:04 Implementing Breadth-First Search (BFS) in C++ and Java 16:01 Breadth-First Search (BFS) is a traversal technique used in graphs. 18:04 BFS algorithm runs on all the neighbors of each node Crafted by Merlin AI.
those who are doing on Codestudio we first have to create adjlist first so here the easy solution to it using set #include void prepareList(unordered_map &adjlist,vector &edges){ for(int i=0;i
Haha I see how you swithed the code between 17:02~17:05 but you should have told the audience rather than chaging the frame. I bet most of them were confused why thier code was not working until they saw you changed the vis[n] with vis[V] because initally I was confused how does your code worked when litrally N is not defined anywhere. and its push_back how does push worked for queue. then I saw the immidiate frame change😂😂 that was sneaky.
Yup u get confused if u pause the video in between, even i got confused then i just watched even i saw that frame where he changed it to V and ya its ohk. We understood it.
What about Directed Graphs, It applies for them too? I think yes, because the adjacency list will only have those edges so we only traverse those edges
I'm confused on the Time complexity, If we know the while loop runs N times and the size of the adjacency list is 2E, It is alright to add them to get the time complexity? like, the while loop runs N times and the for loop overall runs 2E times..??
I am having a question regarding the TC. How can it be O(N+2E). Since, the outer loop runs as long as the queue isn't empty, which means it will run exactly N times and for each vertex or node, we check if the neighbours are visited and if not, we add them to the queue. Now, at each node, we're checking whether it's neighbours are visited or jot which is itself an O(1) operation. So, for N nodes, we are performing operations equal to the degree of a node. How can the TC not be O(n*avg. degree).
Amazing explanation! I have a doubt regarding time complexity 18:34 . For loop is running inside while loop right? So shouldn't we multiply both as: O(n*(2E)) instead of adding both as: O(n) + O(2E). Thanks for the content.
No,it would have been multiplied only when for each node total number of adjacent node is 2*e,but this is not the case,here ultimately we are overall visiting n nodes and for each node,visiting its adjacent nodes,which is total of 2e for total nodes.
nooo!!! you don't know what E is!! E is total no of edges of whole graph in V + E in your n*E, E is no of neighbours of a particular node!!! see... for every node(while loop) you are running "for" loop for number of times==number of its neighbours so in that case you can say n*e but the thing is this -> for every node number of neighbours are different hence we don''t write complexity like you have written while loop n times run karega aur andar wala for loop jo hai, woh in total, sab while loop ka milake, E(total edges in whole graph) times run karega isliye toh add kiya N aur E ko ab clear ho jana chahiye me bhi atka tha ispe 3-4 dinse same concept dijkstra, prims me bhi apply hoga so make sure you understand it!
@@YupIam-f4t not, it will be adding only because 2E is equal to degree of all nodes, not 1 node. so we can't think like for each node, it is taking 2E time and hence it will not be n*2E
16:56 if the start node is not 0 then the list corresponding to node 0 will be empty hence the queue will become empty after 0 is processed and since node 0 do not have neighbours so the for each loop will not be executed so queue will remain empty and bfs will only contain 0 please address this doubt sir
I think bool data type will be better than int data type for visited array because bool data type takes 1 byte whereas int data type takes 4 bytes. And If I am wrong pls correct me :)
understand with the following explanation (just copy-pasted) This is how nodes are connected(assuming undirected graph) : 0 -> 1 ,2, 3 1 -> 0 2 -> 0, 4 3 -> 0 4 -> 2 So, total no. of edges = E = 4 For first while loop , node = 0, edges = 3 Now, before going to the for loop part, u see a constant time operation O(1) --> q.pop( ) This step will be executed every time we enter into while loop. So, for first while loop how many times for loop will execute ?? It will be equal to the no. of edges , here it will be 3. Therefore, total = ( 1 + 3 ) Similarly for all other nodes, this is how it will look : ( 1 + 3 ) + ( 1 + 1 ) + ( 1 + 2 ) + ( 1 + 1 ) + ( 1 + 1 ) = 13 = O ( V + 2 * E ) = O ( 5 + 2 * 4 )
Let's continue the habit of commenting “understood” if you got the entire video.
Do follow me on Instagram: striver_79
Bhaiya next bideo🥺 pls
US
understood
👍🏻
understood
I can proudly say that this summer I watched more tUf lectures than Netflix episodes.
Because your placement season is here
@@aniket6858 What is placement? Is this india
@@Moch117 no, its pakistan.
what is the result ?
Yoh Netfilix ke hovey?😶🌫️
THOSE WHO ARE WORDERING WHY IT IS O(N) + O(2E) NOT O(N*2E)
For each node, the while loop runs multiple times based on the number of edges connected to that node. Here's how it works:
In the first iteration, the loop runs for e1 edges, plus one extra operation for pushing and popping the node.
In the second iteration, it runs for e2 edges, plus one extra operation for pushing and popping, and so on.
Thus, the total time complexity is the sum of all iterations:
(e1 + e2 + ... + en) + (1 + 1 + ... n times).
The sum of all the edges connected to each node is equal to the total number of edges, which is 2E (since each edge is counted twice in an undirected graph). Adding the n push/pop operations gives the final complexity:
O(V + 2E) because e1 + e2 + ... + en = 2E.
So, the overall complexity is O(V + 2E), which simplifies to O(V + E).
Was searching for this thanks ...
Just to summerize ...
the inner for loop runs in O(2E) in total and not for each iteration of while so its O(V) + o(2E)
@@moneshc6887 perfect
I like the way you explain time and space complexities, which actually helps me to analyze my code complexities. Thanks for the explanation.
Just some simple words! No one can beat your DSA teaching style!!
If u r confused about time complexity part, then see the following dry run of the while loop of the qs. he has solved..
This is how nodes are connected(assuming undirected graph) :
0 -> 1 ,2, 3
1 -> 0
2 -> 0, 4
3 -> 0
4 -> 2
So, total no. of edges = E = 4
For first while loop ,
node = 0, edges = 3
Now, before going to the for loop part, u see a constant time operation O(1) --> q.pop( )
This step will be executed every time we enter into while loop.
So, for first while loop how many times for loop will execute ??
It will be equal to the no. of edges , here it will be 3.
Therefore, total = ( 1 + 3 )
Similarly for all other nodes, this is how it will look :
( 1 + 3 ) + ( 1 + 1 ) + ( 1 + 2 ) + ( 1 + 1 ) + ( 1 + 1 )
= 13
= O ( V + 2 * E )
= O ( 5 + 2 * 4 )
Very well explained !
Awesome 👌👌
Thank you
@@mypowerlevelisover9000 🙂
but at the worst case it will be O(n^2) right? since a complete graph have all the vertex with (n-1) edges. which will lead [(1+(n-1))=n] at each while and for loop. since after n times it will become n square. Please confirm this. BTW thanks for the explaination
17:04 i was still wondering where the heck vis[n] came from. edited like a pro
same bro
this code is not running editor is a pro for sure
vis[V] = {0}
same, didn't expect this from him
you are great striver.
Explain such a complex topic in very easy manner.
Your method of teaching is unique, a unique lecture by a unique teacher🙏🙏🙏
Hey Striver! Thank you for creating outstanding content and helping people interested in coding problems worldwide! Please don’t stress yourself out, take a break after this one. It’s not easy to work full time and dedicate time for this.
understood..awesome..most of the youtuber's don't explain a topic in depth... great video
Thank you man from the bottom of my heart for this video. You're one of the greatest instructors i've ever seen
You are amazing 🤩
Guru wo hota h jo muskil si cheez ko v Asan karde tushi great ho ji striver ❤
Are you going to teach leetcode questions just like you did in DP series? It would be very helpful if you can teach commonly asked good questions covering different graph patterns and not just the basic ones.
Yups, this one is going to be 50+ videos.
@@takeUforward bro try to cover as max you can till 15 aug, thnks for helping
after seeing your post on LinkedIn that you are launching graph series 2.0 i used to see your TH-cam playlist daily now I am very happy thank you very much 💗
57 +videos trurly 🇮🇳 biggest graph series Ironically GOAT 🐐 is teaching GRAPH 🤩
17:02 the code he wrote has errors , 17:06 the errors are gone .
coded on my own! Got an error, resolved the issue, all TC passed! Note taken
Toh tujhe kya lg rha bada jhanda gaad diya tune saale itne chappal maruga
Your videos never fail to save us anytime :) Undhan rasigaiyee naaum unaken puriyavillai...
Understood each and every word♥. Kudos to your hard work and dedication, you are the motivation behind a lot of people. Your hardwork inspires a lot of people to work hard.
Thankyou for providing such a beautiful graph series keep posting such content ♥, we all need this.
This guy teachers so fuckin good that if I try seeing DSA related video from any other utube channel it feels something is missing, he's not striver
Awesome Space & Time Analysis 🔥🔥🔥🔥🔥🔥🔥🔥
I was happy to say that I will do and understand first graph problem.🎉
Thank you so much stiver. Happy Teachers dayy
Thanks a lot stiver for putting all these playlists out. i can't imagine getting a job if you were not on youtube. i have a little doubt that in "bfsOfGraph" function the syntax of adj[ ] should be this "Vector> adj [ ]" but it is "vector adj[ ]" instead and this is a 1D vector not a vector of vector.
Here you're creating an array of vector.... basically number of vector is fixed....that is the way to create array of vectors
there is a similar comment in the video number G-2 check that out
Hence, vectoradj[n]
n is no of vertices.(0 based) . adj creates an array where each adj[i] is a vector itself. Array of VECTORS.
Same doubt. if we're storing an array at each index of the vector, shouldn't it be vector adj instead of vectoradj??
@@prachi1112 We are storing vector in array index, i.e array of vectors. Every node of array denotes an array . Eg -> if we write int arr[] , here data type is int , so it is array of integers, but if we write vector arr[] , here data type is vector , so it is array of vector
Time complexity of BFS may be different depending upon representation of graph.
Adjacency List: O(V+E)
Adjacency Matrix: O(V^2)
where V=no of vertex and E = no of edges
00:01 Breadth-First Search (BFS) is a traversal technique in graphs.
02:16 Breadth-first search (BFS) traversal of the graph
04:25 Breadth-First Search (BFS) is a traversal technique in graphs.
06:37 Breadth-First Search (BFS) is a traversal technique in graphs.
08:54 Performing BFS traversal on a graph using adjacency list representation
11:35 BFS traversal of graph
14:04 Implementing Breadth-First Search (BFS) in C++ and Java
16:01 Breadth-First Search (BFS) is a traversal technique used in graphs.
18:04 BFS algorithm runs on all the neighbors of each node
Crafted by Merlin AI.
BEST DSA TEACHER FOR ME
how does adj[node] an int is iterable ? shouldnt it be vector adj in the function definition too?
understood
17:03 i see what you did there 🤣🤣
no one commented on this :(
Understood! Awesome explanation as always, thank you so much!
Thankyou striver bhaiya! ❤️
Lecture successfully completed on 03/12/2024 🔥🔥
Understood, Happy Learning🤗
please also explain space and time complexities
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
There was some sound glitch for 30 sec.. Was weird but
Loved the way you teach and i am here after conpleting your trees playliat... ❤
14:30 program starts
how can someone be so perfect in explianing concept
Nice and crystal clear explanation !!
You are amazing striver ❣️
great content loving this after completing dp series💙💛💙
"UNDERSTOOD BHAIYA!!"
those who are doing on Codestudio we first have to create adjlist first
so here the easy solution to it using set
#include
void prepareList(unordered_map &adjlist,vector &edges){
for(int i=0;i
a well explained and organised lecture !!!
congrats bhaiya for 300k
ek din apan sath me 1m jayenge
here we go !
5/56 done(3.12.22)
Liked the video, notes taken, understood
you are the best stiver
i loved it sir , what a beautiful explanation
Ohoo masthhh bhaiyaaaa Woohoo
My favourite algorithm so far, Breast First Search
understood!! Explained beautifully!!
very well explained with all the minute details
Haha I see how you swithed the code between 17:02~17:05 but you should have told the audience rather than chaging the frame. I bet most of them were confused why thier code was not working until they saw you changed the vis[n] with vis[V] because initally I was confused how does your code worked when litrally N is not defined anywhere. and its push_back how does push worked for queue. then I saw the immidiate frame change😂😂 that was sneaky.
Yup u get confused if u pause the video in between, even i got confused then i just watched even i saw that frame where he changed it to V and ya its ohk. We understood it.
hats off to ur hard work.
Thankuu sooo muchhh broooo🤗🤗🤗❤❤❤❤❤
crystal clear.. excellent explanantion
Fantastic 🎉 Understood
9:39 ASMR moments
What about Directed Graphs, It applies for them too?
I think yes, because the adjacency list will only have those edges so we only traverse those edges
brilliantly explain thanks sir and neeed complete playlist of DSA from you for cracking google like companies
Thanks Bhaiya
I'm confused on the Time complexity,
If we know the while loop runs N times and the size of the adjacency list is 2E, It is alright to add them to get the time complexity?
like, the while loop runs N times and the for loop overall runs 2E times..??
What an amazing explanation! Understood! 🤩❤🔥
made it simple to understand
Thank you, Striver
Thank you sir
I am having a question regarding the TC. How can it be O(N+2E). Since, the outer loop runs as long as the queue isn't empty, which means it will run exactly N times and for each vertex or node, we check if the neighbours are visited and if not, we add them to the queue. Now, at each node, we're checking whether it's neighbours are visited or jot which is itself an O(1) operation. So, for N nodes, we are performing operations equal to the degree of a node. How can the TC not be O(n*avg. degree).
love you from bangladesh
Understood. Thanks a lot.
Understood..next please ✌🏻
Amazing explanation! I have a doubt regarding time complexity 18:34 . For loop is running inside while loop right? So shouldn't we multiply both as:
O(n*(2E)) instead of adding both as: O(n) + O(2E). Thanks for the content.
No,it would have been multiplied only when for each node total number of adjacent node is 2*e,but this is not the case,here ultimately we are overall visiting n nodes and for each node,visiting its adjacent nodes,which is total of 2e for total nodes.
@@amanbhadani8840 2E or E, shouldn't be the number of edges, which was E here in this example?
@@amanbhadani8840 very well addressed brother!!
@@himanshupoddar1395 No, in the case of undirected graph you have to traverse 2*E edges.
Thanks sir .... best solutions
Interesting that you have to set 0 as visited missed that when I first tried it!
There is a small correction between 16:56 and 17:05 , pls re-edit . It will help the beginners, remaining everything is cool stuff ., Striver.
Understood sir❤🙏🙇♂
Wonderful bhaiya.....
Understood Sir, Thank you very much
Thank you very much. You are a genius.
Wont Time Complexity be O(n*2E)?? Since for each node n we are traversing 2E
But once you have travelled for all nodes, all are visited, you won’t again traverse na. Overall you will travel everyone once only
nooo!!!
you don't know what E is!!
E is total no of edges of whole graph in V + E
in your n*E, E is no of neighbours of a particular node!!!
see...
for every node(while loop) you are running "for" loop for number of times==number of its neighbours
so in that case you can say n*e
but the thing is this -> for every node number of neighbours are different hence we don''t write complexity like you have written
while loop n times run karega aur andar wala for loop jo hai, woh in total, sab while loop ka milake, E(total edges in whole graph) times run karega
isliye toh add kiya N aur E ko
ab clear ho jana chahiye
me bhi atka tha ispe 3-4 dinse
same concept dijkstra, prims me bhi apply hoga so make sure you understand it!
@@CuriousAnonDev thanks for indepth explaination !
@@CuriousAnonDev naam dekh kar mai bhi atak gaya
Great explanation
all clear thank u bro
Great series
Isn't the TC is O(N* 2E)? Because we run for loop on each node's degree.
yeah, I got the same doubt. Its multiplication only .
@@YupIam-f4t not, it will be adding only because 2E is equal to degree of all nodes, not 1 node. so we can't think like for each node, it is taking 2E time and hence it will not be n*2E
Woah nice explanation
what if the graph have different components?
the solution seems to solve the connected components only.
16:56 if the start node is not 0 then the list corresponding to node 0 will be empty hence the queue will become empty after 0 is processed and since node 0 do not have neighbours so the for each loop will not be executed so queue will remain empty and bfs will only contain 0 please address this doubt sir
Exactly my thoughts! The implementation seems wrong. It should be q.add(V) & visited[V] = true
Understood 🥳🥳
Understood bhaiya!
This was great, wandering about traversing Graph with starting nodes somewhere in middle. Should that be traversed wrt to levels or some-other way?
just thank you 🙏
I think bool data type will be better than int data type for visited array because bool data type takes 1 byte whereas int data type takes 4 bytes.
And If I am wrong pls correct me :)
ya no issue ... just taking int as it would help with weighted graphs as well and generalize the approach
Thankyou striver!
Great work. Thanks for doing this.
Thank you so much.
Hi @TakeUforward, I had a doubt, when the for loop is inside the while loop, shouldn't we multiply the time complexities instead of adding them?
understand with the following explanation (just copy-pasted)
This is how nodes are connected(assuming undirected graph) :
0 -> 1 ,2, 3
1 -> 0
2 -> 0, 4
3 -> 0
4 -> 2
So, total no. of edges = E = 4
For first while loop ,
node = 0, edges = 3
Now, before going to the for loop part, u see a constant time operation O(1) --> q.pop( )
This step will be executed every time we enter into while loop.
So, for first while loop how many times for loop will execute ??
It will be equal to the no. of edges , here it will be 3.
Therefore, total = ( 1 + 3 )
Similarly for all other nodes, this is how it will look :
( 1 + 3 ) + ( 1 + 1 ) + ( 1 + 2 ) + ( 1 + 1 ) + ( 1 + 1 )
= 13
= O ( V + 2 * E )
= O ( 5 + 2 * 4 )
@@IITiansgreat
thx striver. Understood.
Thank you, understood!