[LeetCode]Evaluate Division

Problem: You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Approach: The trick here is, all the equations or queries are only having divisions. Let's look at some examples:

Say a/b = n and b/c = m then a/c = (a/b) * (b/c) = n * m or (c/a) = (c/b) * (b/a) = (1/m) * (1/n)

and if there are no such relationship then we can't calculate the answer. If in the above example say d/e is given and we want to calculate a/e, it's just not possible.

If you see we can form a graph where nodes are connected to each other if in the equations their division is given. Like if a/b = n then a is connected to b with edge weight n and b is connected to a with edge weight of 1/n.

We can use DFS to find the answer for this question. Here is our graph will look like -

If we want to calculate a/c. We will start our search from a and we do DFS till we reach c. We will keep multiplying our current result with the node weight. If we calculate a/c using the above simple graph, you will see:

• Step1: current_result = 1, source = a, destination = c
• Step 2:  Moved from a to b; current_result = 1 * n = n , source = b, destination = c
• Step 3:  Moved from b to c; current_result = n * m = nm , source = c, destination = c
• Step 4: source and destination are same (c); return current_result = n*m  

That's all about the explanation. My approach is faster than 94.5% of C# submissions. Let's move to implementation.

Implementation in C#:

        public double[] CalcEquation(IList<IList<string>> equations,

                                 double[] values,

                                 IList<IList<string>> queries)

    {

        var equationGraph = this.BuildGraph(equations, values);

        double[] result = new double[queries.Count];

        for(int i = 0; i < queries.Count; ++i)

        {

            HashSet<string> visited = new HashSet<string>();

            string source = queries[i][0];

            string dest = queries[i][1];

            if (equationGraph.ContainsKey(source) &&

                equationGraph.ContainsKey(dest))

            {

                if (source == dest)

                {

                    result[i] = 1.0;

                }

                else

                {

                    result[i] = this.CalcEquationDFS(source,

                                                     dest,

                                                     1.0,

                                                     equationGraph,

                                                     visited);

                   

                }

            }

            else

            {

                result[i] = -1.0;

            }

        }

        return result;

    }

    private double CalcEquationDFS(string src,

                                   string dest,

                                   double currProd,

                                   Dictionary<string, List<KeyValuePair<string, double>>> graph,

                                   HashSet<string> visited)

        {

            if (visited.Contains(src))

            {

                return -1.0;

            }

            if (!graph.ContainsKey(src))

            {

                return -1.0;

            }

            if (src == dest)

            {

                return currProd;

            }

            visited.Add(src);

            foreach(var node in graph[src])

            {

                double prod = this.CalcEquationDFS(node.Key,

                                                   dest,

                                                   currProd * node.Value,

                                                   graph,

                                                   visited);

                if (prod != -1.0)

                {

                    return prod;

                }

            }

            return -1.0;

        }

    private Dictionary<string, List<KeyValuePair<string, double>>> BuildGraph(IList<IList<string>> equations,

                                                                              double[] values)

    {

        var graph = new Dictionary<string, List<KeyValuePair<string, double>>>();

        for(int i = 0; i < equations.Count; ++i)

        {

            var equation = equations[i];

            if (!graph.ContainsKey(equation[0]))

            {

                graph[equation[0]] = new List<KeyValuePair<string, double>>();

            }

            graph[equation[0]].Add(new KeyValuePair<string, double>(equation[1],

                                                                    values[i]));

            if (!graph.ContainsKey(equation[1]))

            {

                graph[equation[1]] = new List<KeyValuePair<string, double>>();

            }

            graph[equation[1]].Add(new KeyValuePair<string, double>(equation[0],

                                                                    1 / values[i]));

        }

        return graph;

    }

Complexity: O(m * n) where m is the number of equations and n is the number of queries.