evaluate division | evaluate division leetcode | leetcode 399 | graph dfs

Problem Link - leetcode.com/explore/challeng...
Subscribe for more educational videos on data structure, algorithms and coding interviews - czcams.com/users/NareshGupta?s...
September Challenge - leetcode.com/explore/challeng...
Code Repository - github.com/naresh1406/youtube...
August LeetCoding Challenge Playlist: • LeetCode August Challenge
July LeetCoding Challenge Playlist: • LeetCode July Challenge
June LeetCoding Challenge Playlist: • LeetCode June Challenge
May LeetCoding Challenge Playlist: • LeetCode May Challenge
LeetCode Recent Contest ProblemsPlaylist: • Leetcode
LinkedIn - / nareshiitg
Instagram - / naresh_gupta_
Facebook - / 2784412725174003
Quora - qr.ae/pN2M0x
#Graph #DFS #Division #Evalute #Code #Interview #Practice #September #Leetcode #Medium #399 #Algorithm #DataStructure #Java #Preparation #NG #nickode #CookCodeTravel #CCT

[@NareshGupta]

Time Complexity - O(Q * (V + E)), where Q - Quereis, V - Number of Vertices, E - Number Edges (length of values).
Space Complexity - O(V + E).

[@vijayalakshmichidambaram9788]

Can you please explain about getting this time and space complexity ?

[@gilbertlopez]

Hey man, just wanna say I enjoy your videos on these monthly challenges! My data structures are a little rusty and other times they help me understand the problem better so these are a huge help and I really hope you continue making them!

[@NareshGupta]

Thanks and welcome to channel, keep watching. Yes, definitely I will.

[@0xVantwoutMaarten]

what a champ, happy I did not have to do this problem on my own ❤‍🔥

[@ikramulmurad]

You're helping me a lot to keep coding!
Whenever I can't get the idea behind any problem, then I immediately search your video on youtube. Even if the problem is very complex, your solution is simple enough to get it.

[@NareshGupta]

Glad to hear that!

[@devindas1669]

Explained clearly and quickly. Well done, brilliant answer. Thank you!

[@NareshGupta]

Glad it was helpful!

[@ankitbatra9832]

Your explanations are really thorough, loved your videos. Keep contributing! :)

[@NareshGupta]

Thank you! Will do! Welcome to Channel.

[@ChristianESL]

you are amazing. I have seen a couple of explanations from your channel and they are good. New subscriber :P

[@NareshGupta]

Thanks and welcome to channel, keep watching and solving ds algo problems.

[@janaarthananselvarajan264]

This is not dfs but a normal recursive function to iterate the hashmap
Dfs deals with a map inside the node and go recursive with the next next nodes.

[@ishaanmarjara4510]

I am a new subscriber but i feel like these are the best explanations out there :)))

[@NareshGupta]

Thanks and welcome to channel, keep watching and sharing.

[@nayankhanna2367]

Thanks a lot, you make look things so easy.

[@NareshGupta]

Thanks and Enjoy Programming

[@TheAuthorityOf]

Excellent explanation

[@theTacoKing640]

Really high-quality explanation. TY!

[@NareshGupta]

Thankyou and welcome to channel

[@saimanojkadiyala]

Why do we need to check if the ans returned is -1.0. Is there any case where the ans is returned as -1.0 after a DFS call.
If any of the vertex is not present in the graph we return -1.0 immediately.
if (ans != -1.0)
return ans * node.val;
EDIT :
There is a scenario where the two vertices belong to two different "connected components" where this check is required.

[@NareshGupta]

You cracked it. Good

[@manishbolbanda9872]

thanks for raising the query and providing the ans as well.

[@beingSenpai]

when we have disconncected graph

[@arpanbanejee5143]

Nice explanation! Thank you!
One suggestion from my side- pls give a dry run first and explain the edge cases as well, like why are we checking the and for -1 even when we have a case to check and return -1 before calling DFS again etc.

[@NareshGupta]

Thanks for feedback, Yes I started in my recent videos.

[@sugandhm2666]

Really good explanation

[@KuldeepSahu-sq3cq]

Great ❤️

[@soumyadipauddy]

please analyze the time complexity after the code also. It will help us in the interviews.

[@NareshGupta]

Actually, I used to do that but today this video become very long and missed that part. Thanks, I will take care from next video, for now, I added in PIN comment.

[@rushio8673]

This code will not work for :
equations =
[["x1","x2"],["x2","x3"],["x3","x4"],["x4","x5"]]
values =
[3.0,4.0,5.0,6.0]
queries =
["x2","x4"]
when going from x2 to x4 it will consider all edges from x2 which also contains an edge from x2 to x1 which is 1/3 and will add that to result calculation as well, so instead of expected answer 20, it returns 0.33

[@nitingoyal5515]

great solution, thanks a lot

[@NareshGupta]

You're welcome!

[@maksoodansari5262]

At line number 23, condition should be OR not AND!

[@JefffffffL]

Thanks for the great solution again!! very clear and easy understanding. I have one question about a test case like [["a","b"],["b","c"],["bc","cd"]], i'm not sure how the graph should be visualized with the case of "bc" and "cd", how are they supposed to be connected with the graph a -> b -> c. Thanks in advance

[@NareshGupta]

Thanks, don't think bc and cd as product of two variables this is new different individuals variables bc, cd are two independent vertices of graph.

[@saimanojkadiyala]

This is where I gave up. The problem just got a lot more complex.

[@garvitkumargupta3306]

@@saimanojkadiyala same

[@vishalgoel6323]

Hi, i have a query suppose
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["ac","ba"]]
It is giving output [6.00000,0.50000,-1.00000]
But i think for query ["ac","ba"] output should be 0.333333 as ac / ba == c/b but instead it is showing -1.00000 ?

[@NareshGupta]

ac, ba is not a * c and b * a it is independent variable and vertices of the graph.

[@vishalgoel6323]

@@NareshGupta Yeah i got it. These are basically variables.

[@AnandKumar-kz3ls]

@@vishalgoel6323 yes thats why inputs are in string otherwise it will be in char

[@osiris1102]

Brilliant video! But the pronunciation of "neighbours" was horrible.

[@NareshGupta]

Thanks for feedback will work on it.

[@AnandKumar-kz3ls]

thanks for the video My CPP solution -
typedef unordered_map Graph;
class Solution {
public:
Graph graph;
void buildGraph(vector& equations,vector& values){
for(int i=0;i

[@Rajat_maurya]

can you explain Graph graph;
and typedef?
btw nice way of writing choosing of variable name properly