Solution For Evaluate Division

Evaluate Division is a problem on leetcode that involves computing the division of two given numbers and storing the result in a graph. The graph can then be used to answer queries about the division of two numbers that are not directly connected.

The following is a detailed solution for the Evaluate Division problem on leetcode:

1. Create a graph using a dictionary:

The first step is to create a graph that contains all the given pair-wise divisions. The graph can be represented as a dictionary where the keys are the nodes (strings) and the corresponding values are dictionaries that contain the neighbor nodes and their respective weights (floats). This can be achieved using the following code:

graph = {}
for dividend, divisor, quotient in equations:
if dividend not in graph:
graph[dividend] = {}
if divisor not in graph:
graph[divisor] = {}
graph[dividend][divisor] = quotient
graph[divisor][dividend] = 1 / quotient

This code loops through the given equations and for each equation creates an entry in the dictionary for each of the nodes (if they don’t already exist). It then adds the quotient as the weight of the directed edge from the dividend to the divisor and its inverse as the weight of the directed edge from the divisor to the dividend.

1. Implement DFS algorithm:

Next, we implement a DFS algorithm to traverse the graph and find the quotient between the two nodes. This can be achieved using the following code:

def dfs(start, end, visited, graph):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
quotient = graph[start][neighbor] temp = dfs(neighbor, end, visited, graph)
if temp != -1.0:
return quotient * temp
return -1.0

This code takes in the start node, end node, a set of visited nodes and the graph as inputs. It first checks if the start and end nodes exist in the graph and returns -1.0 if either of them don’t exist. It then checks if the start and end nodes are the same and returns 1.0 if they are.

If the start and end nodes are not the same, it adds the start node to the set of visited nodes and loops through all its neighbors. For each neighbor, it checks if it has not already been visited and finds the quotient between start and neighbor. It then calls the dfs function recursively with the neighbor as the start node, the end node, and the updated set of visited nodes.

If the recursion returns a value other than -1.0, it multiplies the quotient by this value and returns it. If all neighbors have been visited and the end node has not been found, it returns -1.0.

1. Return the results:

Finally, we call the dfs function for each query and return the results in a list. This can be achieved using the following code:

results = [] for query in queries:
results.append(dfs(query[0], query[1], set(), graph))

This loops through the given queries and for each query, it calls the dfs function with the start and end nodes and an empty set of visited nodes. It then appends the result to a list of results and returns it.

1. Complete solution:

Here is the complete solution in Python:

“`
class Solution:
def calcEquation(self, equations, values, queries):
graph = {}
for (dividend, divisor), quotient in zip(equations, values):
if dividend not in graph:
graph[dividend] = {}
if divisor not in graph:
graph[divisor] = {}
graph[dividend][divisor] = quotient
graph[divisor][dividend] = 1 / quotient

    def dfs(start, end, visited, graph):
        if start not in graph or end not in graph:
            return -1.0
        if start == end:
            return 1.0
        visited.add(start)
        for neighbor in graph[start]:
            if neighbor not in visited:
                quotient = graph[start][neighbor]
                temp = dfs(neighbor, end, visited, graph)
                if temp != -1.0:
                    return quotient * temp
        return -1.0

    results = []
    for query in queries:
        results.append(dfs(query[0], query[1], set(), graph))
    return results

“`

This solution passes all test cases on leetcode.

Step by Step Implementation For Evaluate Division

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        // create a graph where each node is an equation and each edge
        // represents a value
        Map> graph = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            String[] equation = equations[i];
            // get the value of the edge
            double value = values[i];
            // get the two nodes for the edge
            String node1 = equation[0];
            String node2 = equation[1];
            // add the edge to the graph
            graph.computeIfAbsent(node1, k -> new HashMap<>()).put(node2, value);
            graph.computeIfAbsent(node2, k -> new HashMap<>()).put(node1, 1.0 / value);
        }
        // create an array to store the results
        double[] result = new double[queries.length];
        // loop through each query
        for (int i = 0; i < queries.length; i++) {
            // get the two nodes for the query
            String[] query = queries[i];
            String node1 = query[0];
            String node2 = query[1];
            // if the graph doesn't contain either node, the result is -1.0
            if (!graph.containsKey(node1) || !graph.containsKey(node2)) {
                result[i] = -1.0;
            } else {
                // otherwise, use a depth first search to find the value
                result[i] = dfs(graph, node1, node2, new HashSet<>());
            }
        }
        return result;
    }
    
    // depth first search helper function
    private double dfs(Map> graph, String start, String end, Set visited) {
        // if the start node is the same as the end node, the result is 1.0
        if (start.equals(end)) {
            return 1.0;
        }
        // mark the start node as visited
        visited.add(start);
        // get the map of edges for the start node
        Map edges = graph.get(start);
        // loop through each edge
        for (Map.Entry edge : edges.entrySet()) {
            // get the node at the end of the edge
            String node = edge.getKey();
            // if the node has not been visited
            if (!visited.contains(node)) {
                // recursively call depth first search with the end node
                double result = dfs(graph, node, end, visited);
                // if the result is not -1.0, return the result
                if (result != -1.0) {
                    return result * edge.getValue();
                }
            }
        }
        // if there is no valid path, return -1.0
        return -1.0;
    }
}

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        
        # build a graph using the equations and values
        graph = {}
        for i in range(len(equations)):
            x, y = equations[i]
            val = values[i]
            if x in graph and y in graph[x]:
                graph[x][y] = val
                graph[y][x] = 1/val
            elif x not in graph and y not in graph:
                graph[x] = {}
                graph[x][y] = val
                graph[y] = {}
                graph[y][x] = 1/val
            elif x in graph and y not in graph:
                graph[y] = {}
                graph[y][x] = 1/val
                graph[x][y] = val
            elif y in graph and x not in graph:
                graph[x] = {}
                graph[x][y] = val
                graph[y][x] = 1/val
                
        # use dfs to find the product of the edges between two nodes
        def dfs(x, y, visited):
            if x == y:
                return 1.0
            for node in graph[x]:
                if node not in visited:
                    visited.add(node)
                    temp = dfs(node, y, visited)
                    if temp:
                        return temp * graph[x][node]
            return -1.0
        
        # iterate through all queries and find the product for each
        ans = []
        for x, y in queries:
            visited = set()
            if x not in graph or y not in graph:
                ans.append(-1.0)
            else:
                ans.append(dfs(x, y, visited))
        return ans

var evaluateDivision = function(equations, values, queries) {
    // create a map of the equations
    let map = {};
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        // if the key does not exist, create it and set its value to an empty array
        if (!map[a]) {
            map[a] = [];
        }
        // push the equation and its corresponding value into the map
        map[a].push([b, values[i]]);
        // do the same for the inverse equation
        if (!map[b]) {
            map[b] = [];
        }
        map[b].push([a, 1/values[i]]);
    }
    
    // helper function to find the value of an equation
    function findValue(start, end, map, visited) {
        // if the start node does not exist in the map, return -1
        if (!map[start]) {
            return -1;
        }
        // if the start node is the same as the end node, return 1
        if (start === end) {
            return 1;
        }
        // mark the start node as visited
        visited[start] = true;
        // get the array of equations from the map
        const equations = map[start];
        // loop through the equations
        for (let i = 0; i < equations.length; i++) {
            const [node, value] = equations[i];
            // if the node has not been visited yet
            if (!visited[node]) {
                // recursively call the helper function with the node and the end node
                const res = findValue(node, end, map, visited);
                // if the result is not -1, return the value of the equation multiplied by the result
                if (res !== -1) {
                    return res * value;
                }
            }
        }
        // if no equation is found, return -1
        return -1;
    }
    
    // result array
    const res = [];
    // loop through the queries
    for (let i = 0; i < queries.length; i++) {
        const [start, end] = queries[i];
        // create an object to keep track of visited nodes
        const visited = {};
        // call the helper function to find the value of the equation and push it into the result array
        res.push(findValue(start, end, map, visited));
    }
    // return the result array
    return res;
};

class Solution {
public:
    vector calcEquation(vector> equations, vector& values, vector> queries) {
        // Create a graph using the equations and values
        unordered_map> graph;
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            string a = equations[i].first;
            string b = equations[i].second;
            double val = values[i];
            if (!graph.count(a)) {
                graph[a] = unordered_map();
            }
            if (!graph.count(b)) {
                graph[b] = unordered_map();
            }
            graph[a][b] = val;
            graph[b][a] = 1.0 / val;
        }
        
        // DFS to find the path from a to b
        vector result;
        for (auto& query : queries) {
            string a = query.first;
            string b = query.second;
            if (!graph.count(a) || !graph.count(b)) {
                result.push_back(-1.0);
                continue;
            }
            unordered_set visited;
            double val = dfs(graph, a, b, visited);
            if (val == 0.0) {
                result.push_back(-1.0);
            } else {
                result.push_back(val);
            }
        }
        return result;
    }
    
    double dfs(unordered_map>& graph, string& a, string& b, unordered_set& visited) {
        if (a == b) {
            return 1.0;
        }
        visited.insert(a);
        for (auto& neighbor : graph[a]) {
            if (visited.count(neighbor.first)) {
                continue;
            }
            double val = dfs(graph, neighbor.first, b, visited);
            if (val != 0.0) {
                return val * neighbor.second;
            }
        }
        return 0.0;
    }
};

public class Solution {
    public double[] CalcEquation(string[,] equations, double[] values, string[,] queries) {
        // create a graph where each node is an equation and each edge is a value
        var graph = new Dictionary>();
        for (int i = 0; i < equations.GetLength(0); i++) {
            string eq1 = equations[i,0], eq2 = equations[i,1];
            double val = values[i];
            if (!graph.ContainsKey(eq1)) graph[eq1] = new List<(string, double)>();
            if (!graph.ContainsKey(eq2)) graph[eq2] = new List<(string, double)>();
            graph[eq1].Add((eq2, val));
            graph[eq2].Add((eq1, 1.0 / val));
        }
        
        // for each query, do a BFS to find the path from the first equation to the second equation
        // if a path exists, the product of the values along the path is the answer
        // otherwise, the answer is -1.0
        var ans = new double[queries.GetLength(0)];
        for (int i = 0; i < queries.GetLength(0); i++) {
            string eq1 = queries[i,0], eq2 = queries[i,1];
            if (!graph.ContainsKey(eq1) || !graph.ContainsKey(eq2)) {
                ans[i] = -1.0;
                continue;
            }
            var visited = new HashSet();
            var queue = new Queue<(string, double)>();
            queue.Enqueue((eq1, 1.0));
            while (queue.Count > 0) {
                var (node, val) = queue.Dequeue();
                if (node == eq2) {
                    ans[i] = val;
                    break;
                }
                visited.Add(node);
                foreach (var (neighbor, neighborVal) in graph[node]) {
                    if (!visited.Contains(neighbor)) {
                        queue.Enqueue((neighbor, val * neighborVal));
                    }
                }
            }
            if (ans[i] == 0) ans[i] = -1.0;
        }
        return ans;
    }
}