Evaluate Division - Leetcode 399 - Python

[@1000iq_gaming]

This should be a "HARD" problem. Very important one though - many variations.

[@JeffreyConcerto]

People have already thanked you for doing the daily LeetCode problems, but I just wanted to emphasize how truly helpful it is. I do each daily problem, and regardless of whether I can solve the problem myself or not, I come to watch your solution to get a better understanding. Your videos are helping me grow as a programmer and I greatly appreciate that. Thank you!

[@manikdeepak1111]

15:22 we are not doing it for fun got me

[@nihaal4699]

If the interviewer, thinks that i came up with this solution by my own in the interview. Then i am not sure who is more dumb among us.

[@licokr]

I watched it three times. I wouldn't know if I would be able to solve this problem without your explanation. maybe, after putting a lot of time into it. It's really awesome. Thanks a lot

[@yoprstification]

There is a more intuitive way to look at this problem (which leads to the same solution). Instead of a/b=2, b/c=3 consider equations a=2*b, b=3*c. And instead of solving the equation a/c=x, solve this one: a=x*c. The solution is quite intuitive: a = 2 * b = 2 * (3 * c) = 6 * c. The opposite direction is the same with different coefficients: c = 1/3 * b = 1/3 * (1/2 * a) = 1/6 * a.

[@ancai5498]

For anyone wants a DFS solution: The idea is the same, mainly the base case, once we reach src == dst, we return 1, means we found the match. And, if the src is not in the adjs, we'll return -1 immediately, another case is if the nei is not in the src's adjs, then we'll return -1 at the end of the for loop as well. vector calcEquation(vector& equations, vector& values, vector& queries) { unordered_map adjs; for (int i = 0; i < equations.size(); i++) { adjs[equations[i][0]].push_back({equations[i][1], values[i]}); adjs[equations[i][1]].push_back({equations[i][0], 1 / values[i]}); } vector res; for (auto q: queries) { unordered_set visited; double val = dfs(q[0], q[1], adjs, visited); res.push_back(val); } return res; } double dfs(string src, string dst, unordered_map& adjs, unordered_set& visited) { if (adjs.find(src) == adjs.end()) { return -1; } // match found if (src == dst) { return 1; } visited.insert(src); double res = 1; for (auto nei: adjs[src]) { // avoid loop, a -> b, b -> a. if (visited.count(nei.first)) { continue; } double t = dfs(nei.first, dst, adjs, visited); if (t != -1) { res = t * nei.second; return res; } } return -1; }

[@anusree8707]

thanks!

[@DipakKawale]

class Solution { public double[] calcEquation(List equations, double[] values, List queries) { Map adj = new HashMap(); for (int i = 0; i < equations.size(); i++) { List eq = equations.get(i); String a = eq.get(0); String b = eq.get(1); double value = values[i]; adj.putIfAbsent(a, new ArrayList()); adj.putIfAbsent(b, new ArrayList()); adj.get(a).add(new Pair(b, value)); adj.get(b).add(new Pair(a, 1 / value)); } double[] results = new double[queries.size()]; for (int i = 0; i < queries.size(); i++) { List q = queries.get(i); String src = q.get(0); String target = q.get(1); results[i] = bfs(adj, src, target); } return results; } private double bfs(Map adj, String src, String target) { if (!adj.containsKey(src) || !adj.containsKey(target)) { return -1.0; } Queue queue = new LinkedList(); Set visited = new HashSet(); queue.add(new Pair(src, 1.0)); visited.add(src); while (!queue.isEmpty()) { Pair pair = queue.poll(); String node = pair.getKey(); double weight = pair.getValue(); if (node.equals(target)) { return weight; } for (Pair neighbor : adj.get(node)) { String nei = neighbor.getKey(); double neiWeight = neighbor.getValue(); if (!visited.contains(nei)) { queue.add(new Pair(nei, weight * neiWeight)); visited.add(nei); } } } return -1.0; } }

[@aadityakiran_s]

Thanks man, your solutions are really high quality and well explained. Sometimes I think I don't really have to take LC premium and just solve the questions that you've solved already.

[@princeakhil208]

without looking into the code I am able to solve the problem using the explanation thanks for providing the insights your content is invaluable.

[@MP-ny3ep]

Thank you for the daily leetcode problems!

[@slayerzerg]

i did this problem and came up with the exact logical approach you did using weights of the denominator stored in a dictionary. looks like your videos have rubbed off on me haha. i used dfs but i like your bfs version it seems easier to step through in an interview

[@niladriroy]

I also found DFS to be more natural solution in this case

[@shreshthkaushik-hu8bz]

This solution might be helpful. Its same as neetcode is doing but I tried to comment and do stuff that would make it more clearer ( I guess ) ``` """ From the first example :- equations = [["a","b"],["b","c"]] values = [2.0,3.0] queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] a / b = 2.0 b / c = 3.0 If we notice, we can put these equations in a graph where the edges denote a divide by and the verticies denote the nodes the divde runs between. For our example, the graph would look like a -> b -> c But each edge also denotes the weight, which is nothing but the value of division between two integers. Taking that into mind we get a graph like this 2.0 3.0 a --> b --> c But when we come reverse, let's say c / b then b / a, the weights need to be flipped too and that makes the graph look like this 2.0 3.0 a --> b --> c 1/2 1/3 """ class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: # Create a dictionary/adjacency list to form a map of each numerator to denominator + value # Looks like this - {"a" : [["b", 2.0]], "b" : [["c", 3.0]]} adjacency_list = {} for curr_index, equation in enumerate(equations): numerator = equation[0] denominator = equation[1] divide_value = values[curr_index] # if we go left to right in the graph if numerator not in adjacency_list: adjacency_list[numerator] = [[denominator, divide_value]] else: adjacency_list[numerator].append([denominator, divide_value]) # if we go right to left in the graph if denominator not in adjacency_list: adjacency_list[denominator] = [[numerator, 1 / divide_value]] else: adjacency_list[denominator].append([numerator, 1 / divide_value]) # At this point our adjacency list is formed which looks like # {'a': [['b', 2.0]], 'b': [['a', 0.5], ['c', 3.0]], 'c': [['b', 0.3333333333333333]]} # Create a BFS function where we put a source and a target and it will return the value found for it. # Example : a (source) / c (target) def bfs(source: str , target: str) -> int: # If our source or target doesn't even exist in the adjacency_list then we can simply return -1 if source not in adjacency_list or target not in adjacency_list: return -1.00000 # Create a deque and a set to keep track of visited numerators queue, visited = deque(), set() # Start the queue with source and its weight ( start at 1 ) queue.append([source, 1]) # Also mark this numerator as visited. visited.add(source) # Start going through each source value in the queue until its not empty while queue: element, weight_so_far = queue.popleft() # If we have found the target, simply return if element == target: return weight_so_far # If this is not the target then look for the neighbor in adjacency list for this element for neighbor, weight in adjacency_list[element]: if neighbor not in visited: queue.append([neighbor, weight_so_far * weight]) visited.add(neighbor) # If we didn't find the target, means we cannot possibly compute this return -1.00000 # Run the bfs on each of the given queries return [bfs(source=query[0], target=query[1]) for query in queries] ```

[@YT.Nikolay]

liked before watching, this problem drives me crazy :(

[@advaitdanade7538]

I am very happy that I solved such a tough problem on my own and that too the same way he explained😊

[@kartikeyrana3736]

am i growing dumber by the day or are these medium questions becoming harder and harder. I couldn't even think of a brute-force solution :( @NeetCodeIO were you able to solve this question on your own ?

[@acceleratorlevel645]

no, i think this one is harder than usual mediums

[@Yanqiaochen-c2g]

Great explanation! However, seems like variable visit was not maintained when BFS

[@gilesbbb]

Very satisfying problem and nicely explained solution. Thank you!

[@ShikaIE]

Yea im really weirded out by the x/x. My initial code can handle and return 1.

[@AdityaKanfade]

How does bc/cd get inserted in the graph?

[@shantanudash5217]

Flawless explanation Sir!!

[@vishnuvardhan2687]

Aliens 👽👽 attendance taken by here :) :) :)

[@netanelkomm5636]

Thanks to you I was able to better understand it and I finished it 5 minutes before the deadline.

[@arhitakundu5846]

God bless you!

[@prashantgupta9502]

class Solution { public: typedef pairipair; typedef double ll; bool dfs(int node,int target,vectoradj,ll ans,vector&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 calcEquation(vector& equations, vector& values, vector& queries) { int m=equations.size(); vectoradj(m); mapmp; int node=0; for(int i=0;i

[@CS_n00b]

this is similar to the jane street mock interview

[@anishkarthik4309]

Could you please also post this today problem using union find, if possible.

[@stillfiguringout]

Yeah, a solution for this problem with union find will be much appreciated

[@adithyang6672]

Bhai bfs se hi mushkil se huva abb union find kaha se lagaye

[@bereketyisehak5584]

2:12: me after getting the idea i can use graphs but dk how to code bfs/dfs for weighted directed graph

[@rithickchowdhury7116]

Reading the desc gave me a headache 🤯🤯

[@РоманБледнов-ъ9и]

Hi guys, just wondering how this gonna solev such edge cases: 1) [a/bc] = 2, query [a/cb] -- answer is 2, income is valid, but how we knew 'bc' is the same as 'cb'? 2) [ab/bc] = 2, query[a/c]. -- answer is 2, income is valid, how this approach solve it? @NeetCodeIO pls help

[@Kv-kk2nj]

Me before watching the video 😮 WHY , WHY SHOULD I SOLVE After watching this video .... OK... ITS NOT THAT HARD😅😅

[@edwardteach2]

U a Math God

[@bag_of_pixels]

hope i'll remember something from this solution...

[@yapjiahong]

Yours video is really helpful!! ❤ Thank you

[@piyushsharma1638]

This was solved in 1.5x :)

[@andrewcenteno3462]

There is 0 chance you could solve this at an interview without knowing it prior. Even with hints, the question is so poorly phrased.

[@krateskim4169]

Thank you

[@armandmugabo1170]

just woooo😱

[@Dobby_zuul]

8:39 it's reciprocal not inverse

[@ADITYA-fk1zy]

in test case : 1 the reason i think [ "x, "x" ] is -1.0 is because "x" doesn't exist in any of the equations. java version here: class Solution { public double bfs(String src,String target,Map graph) { if(!graph.containsKey(src) || !graph.containsKey(target)) return -1.0; if(src.equals(target)) { return 1.0; } Queue q = new LinkedList(); q.add(new Pair(src,1.0)); Map visited = new HashMap(); while(!q.isEmpty()) { Pair pair = q.poll(); String n = pair.getKey(); double w = pair.getValue(); visited.put(n,true); if(n.equals(target)) return w; for(String nei :graph.get(n).keySet()) { if(!visited.containsKey(nei)) { q.offer(new Pair(nei, w * graph.get(n).get(nei))); visited.put(nei,true); } } } return -1; } public double[] calcEquation(List equations, double[] values, List queries) { Map graph = new HashMap(); for(int i = 0;i < equations.size();i++) { List eq = equations.get(i); String a = eq.get(0); String b = eq.get(1); if(!graph.containsKey(a)) graph.put(a,new HashMap()); graph.get(a).put(b,values[i]); if(!graph.containsKey(b)) graph.put(b,new HashMap()); graph.get(b).put(a,1 / values[i]); } double[] res = new double[queries.size()]; Arrays.fill(res,-1.0); for(int i = 0;i < queries.size();i++) { List query = queries.get(i); String a = query.get(0); String b = query.get(1); res[i] = bfs(a,b,graph); } return res; } }

[@ladydimitrescu1155]

I think regardless of whether the number is in the question or not, if the number isn’t zero(which the description confirms), said number divided by itself should be zero

[@rakhmadinakmaldaulay79]

​@@ladydimitrescu1155 number divided by itself should be 1, not zero

[@GeneralistDev]

hey, do you know hindi ?

[@shay2559]

I just watched related topics as graph and I immediately got the intuition and logic for the problem.