Evaluate Division

399.Evaluate Division

Graph

Depth-First Search

Hash Table

Problem Statement:

You are given equations in the format A/B=k where A and B are variables represented as strings and k is a real number. Given some queries, return the result of the queries. If a query is impossible, return -1.0.

Example:

Input:

equations = [["a","b"],["b","c"]]
values = [2.0,3.0]
queries = [["a","c"],["b","a"]]

→

Output:

[6.0,0.5]

Algorithm:

1. Build graph using equations and values
2. For each query, perform DFS to find path
3. Multiply weights along path
4. Handle invalid queries with -1.0

Complexity:

Time: O(Q * (V+E)) | Space: O(V+E) where Q is queries, V vertices, E edges

Java Solution:

public double[] calcEquation(List> equations, double[] values, List> queries) {
    // Build graph from equations
    Map> graph = buildGraph(equations, values);
    double[] result = new double[queries.size()];
    
    // Process each query using DFS
    for (int i = 0; i < queries.size(); i++) 
        result[i] = getPathWeight(queries.get(i).get(0), 
                                queries.get(i).get(1), 
                                new HashSet<>(), 
                                graph);
    
    return result;
}

private double getPathWeight(String start, String end, 
        Set visited, Map> graph) {
    
    // Node doesn't exist in graph
    if (!graph.containsKey(start)) 
        return -1.0;
    
    // Direct edge exists
    if (graph.get(start).containsKey(end))
        return graph.get(start).get(end);
    
    // Try all neighbors
    visited.add(start);
    for (String neighbor : graph.get(start).keySet()) {
        if (!visited.contains(neighbor)) {
            double productWeight = getPathWeight(neighbor, end, visited, graph);
            if (productWeight != -1.0)
                return graph.get(start).get(neighbor) * productWeight;
        }
    }
    
    return -1.0;
}

private Map> buildGraph(
        List> equations, double[] values) {
        
    Map> graph = new HashMap<>();
    String u, v;
    
    // Build bidirectional graph with weights
    for (int i = 0; i < equations.size(); i++) {
        u = equations.get(i).get(0);
        v = equations.get(i).get(1);
        
        graph.putIfAbsent(u, new HashMap<>());
        graph.putIfAbsent(v, new HashMap<>());

        graph.get(u).put(v, values[i]);
        graph.get(v).put(u, 1 / values[i]);
    }
    
    return graph;
}

Python Solution:

def calcEquation(self, equations: List[List[str]], values: List[float], 
             queries: List[List[str]]) -> List[float]:
    
    def buildGraph(equations, values):
        graph = defaultdict(dict)
        for (u, v), val in zip(equations, values):
            graph[u][v] = val
            graph[v][u] = 1/val
        return graph
    
    def dfs(start, end, visited):
        if not start in graph:
            return -1.0
        if start == end:
            return 1.0
            
        visited.add(start)
        for neighbor, val in graph[start].items():
            if neighbor not in visited:
                prod = dfs(neighbor, end, visited)
                if prod != -1.0:
                    return val * prod
        return -1.0
    
    graph = buildGraph(equations, values)
    return [dfs(q[0], q[1], set()) for q in queries]

C++ Solution:

vector<double> calcEquation(vector>& equations, 
    vector<double>& values, vector>& queries) {
    
    unordered_mapdouble>> graph;
    
    // Build graph
    for (int i = 0; i < equations.size(); i++) {
        string u = equations[i][0], v = equations[i][1];
        graph[u][v] = values[i];
        graph[v][u] = 1/values[i];
    }
    
    vector<double> result;
    
    // Process queries
    for (const auto& query : queries) {
        unordered_set visited;
        result.push_back(dfs(query[0], query[1], visited, graph));
    }
    
    return result;
}

double dfs(string start, string end, 
    unordered_set& visited,
    unordered_mapdouble>>& graph) {
    
    if (!graph.count(start)) return -1;
    if (graph[start].count(end)) return graph[start][end];
    
    visited.insert(start);
    
    for (const auto& neighbor : graph[start]) {
        if (!visited.count(neighbor.first)) {
            double prod = dfs(neighbor.first, end, visited, graph);
            if (prod != -1)
                return neighbor.second * prod;
        }
    }
    
    return -1;
}