399. Evaluate Division – Leetcode Solutions

Example 1:

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 ]
note: x is undefined => -1.0

Example 2:

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]

Example 3:

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]

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Step 1: Build the graph
        graph = {}
        
        for (A, B), value in zip(equations, values):
            if A not in graph:
                graph[A] = {}
            if B not in graph:
                graph[B] = {}
            # Add both forward and backward edges
            graph[A][B] = value
            graph[B][A] = 1 / value
        
        # Step 2: Helper function to perform DFS
        def dfs(current: str, target: str, visited: set, acc_product: float) -> float:
            # If the current node is the target node, return the accumulated product
            if current == target:
                return acc_product
            
            # Mark the current node as visited
            visited.add(current)
            
            # Explore neighbors
            for neighbor, value in graph[current].items():
                if neighbor not in visited:
                    # Recursively call DFS for neighbors
                    result = dfs(neighbor, target, visited, acc_product * value)
                    if result != -1.0:  # If a valid result is found, return it
                        return result
            
            # If no path is found, return -1.0
            return -1.0
        
        # Step 3: Process each query
        results = []
        for C, D in queries:
            if C not in graph or D not in graph:
                results.append(-1.0)  # Either C or D is not in the graph
            elif C == D:
                results.append(1.0)  # C / C = 1.0
            else:
                results.append(dfs(C, D, set(), 1.0))  # Perform DFS to find the result
        
        return results

class Solution {
public:
    // Function to calculate the division results for the queries
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // Step 1: Create a graph to represent the equations
        unordered_map<string, vector<pair<string, double>>> graph;
        buildGraph(equations, values, graph);

        // Step 2: Process each query and calculate the result
        vector<double> results;
        for (const auto& query : queries) {
            const string& numerator = query[0];
            const string& denominator = query[1];

            // If either variable does not exist in the graph, result is -1.0
            if (graph.find(numerator) == graph.end() || graph.find(denominator) == graph.end()) {
                results.push_back(-1.0);
            } else {
                unordered_set<string> visited;
                double result = -1.0;
                if (numerator == denominator) {
                    result = 1.0; // Same variable division is always 1.0
                } else {
                    result = dfs(graph, numerator, denominator, visited);
                }
                results.push_back(result);
            }
        }

        return results;
    }

private:
    // Function to build the graph from the equations and values
    void buildGraph(vector<vector<string>>& equations, vector<double>& values,
                    unordered_map<string, vector<pair<string, double>>>& graph) {
        for (size_t i = 0; i < equations.size(); ++i) {
            const string& numerator = equations[i][0];
            const string& denominator = equations[i][1];
            double value = values[i];

            // Add edge numerator -> denominator
            graph[numerator].emplace_back(denominator, value);
            // Add edge denominator -> numerator (inverse relation)
            graph[denominator].emplace_back(numerator, 1.0 / value);
        }
    }

    // Depth-First Search to find the value of numerator/denominator
    double dfs(unordered_map<string, vector<pair<string, double>>>& graph,
               const string& current, const string& target,
               unordered_set<string>& visited) {
        if (current == target) return 1.0; // Found target

        visited.insert(current);

        for (const auto& neighbor : graph[current]) {
            const string& nextNode = neighbor.first;
            double value = neighbor.second;

            // Avoid revisiting nodes
            if (visited.find(nextNode) == visited.end()) {
                double result = dfs(graph, nextNode, target, visited);
                if (result != -1.0) { // If a valid path exists, multiply and return
                    return result * value;
                }
            }
        }

        return -1.0; // No valid path found
    }
};

var calcEquation = function(equations, values, queries) {
    // Step 1: Create a graph to represent the equations
    const graph = {};

    // Helper function to add edges to the graph
    const addEdge = (from, to, value) => {
        if (!graph[from]) graph[from] = [];
        graph[from].push([to, value]);
    };

    // Build the graph
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        const value = values[i];
        addEdge(a, b, value);       // Add edge a -> b with weight value
        addEdge(b, a, 1 / value);  // Add edge b -> a with weight 1 / value
    }

    // Step 2: Solve queries using DFS
    const dfs = (start, end, visited) => {
        // If the node is not in the graph, return -1
        if (!graph[start]) return -1.0;
        // If the start and end are the same, return 1
        if (start === end) return 1.0;

        visited.add(start);

        for (let [neighbor, value] of graph[start]) {
            if (visited.has(neighbor)) continue; // Skip visited nodes
            const result = dfs(neighbor, end, visited);
            if (result !== -1.0) {
                return result * value; // Multiply the current value with the result from neighbor
            }
        }

        return -1.0; // If no path is found, return -1
    };

    // Process each query
    const results = [];
    for (let [c, d] of queries) {
        if (c === d && graph[c]) {
            results.push(1.0); // If querying the same variable, the result is 1
        } else {
            results.push(dfs(c, d, new Set())); // Perform DFS for each query
        }
    }

    return results;
};

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // Map to store the graph as adjacency list
        Map<String, Map<String, Double>> graph = new HashMap<>();

        // Step 1: Build the graph
        for (int i = 0; i < equations.size(); i++) {
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);
            double value = values[i];

            // Add the edge var1 -> var2
            graph.putIfAbsent(var1, new HashMap<>());
            graph.get(var1).put(var2, value);

            // Add the edge var2 -> var1 (reciprocal)
            graph.putIfAbsent(var2, new HashMap<>());
            graph.get(var2).put(var1, 1.0 / value);
        }

        // Step 2: Process each query
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0);
            String end = queries.get(i).get(1);

            // If either variable is not in the graph, return -1.0
            if (!graph.containsKey(start) || !graph.containsKey(end)) {
                results[i] = -1.0;
            } else if (start.equals(end)) {
                // If both variables are the same, the answer is 1.0
                results[i] = 1.0;
            } else {
                // Perform BFS/DFS to find the path from start to end
                Set<String> visited = new HashSet<>();
                results[i] = dfs(graph, start, end, 1.0, visited);
            }
        }

        return results;
    }

    // Helper function to perform DFS
    private double dfs(Map<String, Map<String, Double>> graph, String current, String target, double value, Set<String> visited) {
        // Mark the current node as visited
        visited.add(current);

        // If the target is found, return the accumulated value
        if (graph.get(current).containsKey(target)) {
            return value * graph.get(current).get(target);
        }

        // Explore neighbors
        for (Map.Entry<String, Double> neighbor : graph.get(current).entrySet()) {
            String nextNode = neighbor.getKey();
            double edgeWeight = neighbor.getValue();

            if (!visited.contains(nextNode)) {
                double result = dfs(graph, nextNode, target, value * edgeWeight, visited);
                if (result != -1.0) {
                    return result; // Return valid result if found
                }
            }
        }

        // If no path is found, return -1.0
        return -1.0;
    }
}