Evaluate Division - Leetcode 399 - Python

Solving leetcode 399 - evaluate division, today's daily leetcode problem on may 19.

0:00 - Read the problem
1:30 - Drawing Explanation
10:15 - Coding Explanation

leetcode 399

#neetcode #leetcode #python

[Ice-]

If we have a single connected component then, we can do one bfs, calculate value of other variables assuming a = 1, and then ans every query in O(1),
So the TC = O(V + E).

Or even when we have two or more components, we can do a path compression find to check if the two nodes are in the same component. If they are not, return -1 else, you can ans the query.

For every component we have the leader node which is the reference, value of other nodes in the component are calculated from the graph traversal.

So even with multiple components in the graph, we can ans query pretty efficiently in O(1)

[MP-nyep]

Thank you for the daily leetcode problems!

[Ice-]

If we have a single connected component then, we can do one bfs, calculate value of other variables assuming a = 1, and then ans every query in O(1),
So the TC = O(V + E).

[humblecoder]

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

[vickyvilliers]

Nice explanation, but I think we need to have a separate method that simplifies the input and returns the resultant incase if we get the input like ab/bc or ab/c etc...

[ayah]

Thank you! Your explanations really help me understand the intuition.

[vishnuvardhan]

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

[CS_nb]

this is similar to the jane street mock interview

[AdityaKanfade]

How does bc/cd get inserted in the graph?

[debstutidas]

I guess 0/0 is not 1, thats why x/x is -1 (undefined) as we don't know what is the value of x

[alex_p_]

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

[ADITYA-fkzy]

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<String, Map<String, Double>> graph)
{

if(!graph.containsKey(src) || !graph.containsKey(target))
return -1.0;

if(src.equals(target)) {
return 1.0;
}
Queue<Pair<String, Double>> q = new LinkedList<>();

q.add(new Pair<>(src, 1.0));
Map<String, Boolean> visited = new HashMap<>();

while(!q.isEmpty())
{
Pair<String, Double> 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())
{

{
q.offer(new Pair<>(nei, w * graph.get(n).get(nei)));
visited.put(nei, true);
}
}
}

return -1;

}
public double[] equations, double[] values, List<List<String>> queries) {

Map<String, Map<String, Double>> graph = new HashMap<>();

for(int i = 0;i < equations.size();i++)
{
List<String> 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<String> query = queries.get(i);
String a = query.get(0);
String b = query.get(1);

res[i] = bfs(a, b, graph);

}

return res;
}
}