Evaluate Division || Array - Math - Graphs || DFS || Graph Theory || Leetcode 399 || C++/Java/Python

In this video, I'll talk about how to solve leetcode 399. Evaluate Division

Evaluate Division || Array - Math - Graphs || DFS || Graph Theory || Leetcode 399 || C++/Java/Python

Let's Connect:

🛍️ Products I use in Videos: (✨ Marked for Mostly requested Products)

Resources you can try:

🎥Channel Playlists

About Channel:
We teach about how you can grow in life & educate about programming in Fun & Intuitional way.

About Me:
I am Aryan Mittal - a Software Engineer, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)

✨ Timelines✨
0:00 - Bakwas
1:00 - Problem Explanation
4:20 - Intuition & Logic
12:50 - Shall we optimize?
15:27 - In depth code Explanation
26:00 - Complexity Analysis & Bakwas

✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[ARYANMITTAL]

It is one of THE BEST Graph Intuition Problem, i have seen lately, so do solve this one 😎, and haan questions solve ho rahe hai rooj, yaa skip maar rahe ho 😒????

[sakshidevi]

I have a title for you Aryan: CUTE PROGRAMMER

[jagratgupta]

Really nice explaination sir hard to get the intutiion and after that it is a task to store the graph and apply dfs
also the vis array is stored in a set so that find in O(1)...great explaination sir and great problem

[ayushbhandarkar]

Man once again ! What a great explanation !

[shounakbanerjee]

Does it fail due to precision issue for long chain operations?

[himaniupadhyay]

awesome sir u soo much for providing us regular vdos with best explanation
sir plzz also suggest some good projects which can boost up our resume

[comradepeter]

This is why you should always look up solutions after solving them. Like Aryan I also did it by DFS/BFS (BFS to be precise), and when I looked up solutions on LC, people have done it by Union-Find. I recommend you guys think how you would do it by UF, or look up that solution. It's brilliant.
EDIT: Also I recommend first converting all the variable names to some integer, i.e get some mapping from string -> ID. This will massively simplify your workflow and graph. I did it this way.

[jakartaxx-rqkv]

I upvoted for the quality.

I am watching this on x1.25 and I really wish you utilized better intonation instead of rambling bursts that last for multiple seconds.

[princekoshti]

Hey Aryan ... But what about equations having ab/cd and d/b and we want to calculate a/c .. in this case surely the algo won't find a and c in the map and hence store -1.0 in the ans !!!

[prashantgupta]

class Solution {
public:
typedef pair<int, double>ipair;
typedef double ll;
bool dfs(int node, int target, vector<vector<ipair>>adj, ll ans, vector<int>&vis){
if(node==target)return 1;
vis[node]=1;
for(auto it:adj[node]){

ll child=it.first;
ll wt=it.second;
if(vis[child])continue;
ans*=wt;
if(dfs(child, target, adj, ans, vis))return 1;
}
return 0;
}
vector<double> equations, vector<double>& values, vector<vector<string>>& queries) {

int m=equations.size();
vector<vector<ipair>>adj(m);
map<string, int>mp;
int node=0;

for(int i=0;i<m;i++){
string s1="";
string s2="";
int n=equations[i].size();
for(int j=0;j<n;j++){
if(j==0)s1=equations[i][j];
else s2=equations[i][j];





mp[equations[i][j]]=node;
node++;
cout<<node<<endl;
}

}
if(values[i]!=0.0){
adj[mp[s1]].push_back({mp[s2], values[i]});
adj[mp[s2]].push_back({mp[s1], 1.0/(values[i])});
}
}
vector<ll>val;

for(auto it:queries){
ll start=mp[it[0]];
ll target=mp[it[1]];
ll
vector<int>vis(2*node, 0);

if(dfs(start, target, adj, ans, vis)) val.push_back(ans);

else

}
return val;
}
}; This code gives runtime error if I comment the line node++ runtime error is gone why

[VISHALMISHRA-ffih]

How the map here is dealing with a/a, b/b, c/c and so on part ??
If in equation we don't have a/a, b/b like this but a and b is there so out build graph will not store a->a, b->b then the answer will be -1. How you are dealing with this type of query ?? Do we need to write that if a is present then any query a/a will be 1 directly ?

[justajay]

Great Solution bhrother, BTW do you have any discord sever where we can connect to you if not please make one brother, plz