Evaluate Division

Problem Statement

You are given an array of variable pairs equations where equations[i] = [ai, bi] and an array of real numbers values where values[i] represents the value of ai / bi. You are also given some queries where queries[j] = [cj, dj].

For each query, calculate the value of cj / dj and return the answer. If a single answer cannot be determined, return -1.0.

What to notice first

• Build a graph where each variable is a node and each equation defines an edge with a weight (the ratio).
• From a / b = 2, we know a = 2*b and b = 0.5*a.
• For a query c / d, find a path from c to d and multiply the edge weights.

Examples

equations	values	queries	Output	Explanation
[["a","b"],["b","c"]]	[2.0,3.0]	[["a","c"],["b","a"],["a","e"]]	[6.0,0.5,-1.0]	a/b=2, b/c=3 → a/c=6. b/a=0.5. a/e=-1 (not connected)
[["a","b"]]	[0.5]	[["a","b"],["b","a"],["c","c"]]	[0.5,2.0,1.0]	a/b=0.5, b/a=2, c/c=1
[["x1","x2"],["x2","x3"]]	[2.0,3.0]	[["x1","x3"],["x3","x1"]]	[6.0,0.166...]	x1/x3=6, x3/x1≈0.167

Constraints

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= len(equations[i][j]) <= 5
• -100.0 < values[i] <= 100.0
• All equations are unique, answers are at most 10^5 in absolute value

Real-World Applications

Where this pattern appears

• Social network analysis and friend recommendations
• Route planning and GPS navigation
• Dependency resolution and build systems
• Recommendation systems and collaborative filtering

Complexity Comparison

Approach	Time	Space	Notes
DFS	O(n)	O(n)	First approach
Union-Find	O(n)	O(n)	Second approach

Approach 1: DFS

★ Recommended

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

evaluate_division_dfs.py

def calcEquation(equations, values, queries):
    graph = {}
    for (a, b), val in zip(equations, values):
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append((b, val))
        graph[b].append((a, 1.0 / val))

    def dfs(start, end, visited):
        if start not in graph or end not in graph:
            return -1.0
        if start == end:
            return 1.0

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

    return [dfs(a, b, set()) for a, b in queries]

C++

evaluate_division_dfs.cpp

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, vector<pair<string, double>>> graph;
        for (int i = 0; i < equations.size(); i++) {
            graph[equations[i][0]].push_back({equations[i][1], values[i]});
            graph[equations[i][1]].push_back({equations[i][0], 1.0 / values[i]});
        }

        vector<double> result;
        for (auto& query : queries) {
            unordered_set<string> visited;
            result.push_back(dfs(graph, query[0], query[1], visited));
        }
        return result;
    }

private:
    double dfs(unordered_map<string, vector<pair<string, double>>>& graph, string start, string end, unordered_set<string>& visited) {
        if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) return -1.0;
        if (start == end) return 1.0;

        visited.insert(start);
        for (auto& [next, weight] : graph[start]) {
            if (visited.find(next) == visited.end()) {
                double result = dfs(graph, next, end, visited);
                if (result != -1.0) return result * weight;
            }
        }
        return -1.0;
    }
};

Java

EvaluateDivisionDfs.java

import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            graph.putIfAbsent(a, new HashMap<>());
            graph.putIfAbsent(b, new HashMap<>());
            graph.get(a).put(b, values[i]);
            graph.get(b).put(a, 1.0 / values[i]);
        }

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String x = queries.get(i).get(0);
            String y = queries.get(i).get(1);
            if (!graph.containsKey(x) || !graph.containsKey(y)) {
                result[i] = -1.0;
            } else {
                result[i] = dfs(x, y, 1.0, graph, new HashSet<>());
            }
        }
        return result;
    }

    private double dfs(String curr, String target, double prod, Map<String, Map<String, Double>> graph, Set<String> visited) {
        if (curr.equals(target)) return prod;
        visited.add(curr);
        for (String next : graph.get(curr).keySet()) {
            if (!visited.contains(next)) {
                double res = dfs(next, target, prod * graph.get(curr).get(next), graph, visited);
                if (res != -1.0) return res;
            }
        }
        return -1.0;
    }
}

JavaScript

evaluate_division_dfs.js

function solution() { return 0; }
module.exports = solution;

Rust

evaluate_division_dfs.rs

use std::collections::HashMap;

impl Solution {
    pub fn calc_equation(equations: Vec<Vec<String>>, values: Vec<f64>, queries: Vec<Vec<String>>) -> Vec<f64> {
        let mut graph: HashMap<String, Vec<(String, f64)>> = HashMap::new();

        for (i, eq) in equations.iter().enumerate() {
            let a = &eq[0];
            let b = &eq[1];
            let val = values[i];

            graph.entry(a.clone()).or_insert_with(Vec::new).push((b.clone(), val));
            graph.entry(b.clone()).or_insert_with(Vec::new).push((a.clone(), 1.0 / val));
        }

        let mut result = Vec::new();
        for query in queries {
            let x = &query[0];
            let y = &query[1];

            if !graph.contains_key(x) || !graph.contains_key(y) {
                result.push(-1.0);
            } else {
                let mut visited = std::collections::HashSet::new();
                let res = dfs(x, y, 1.0, &graph, &mut visited);
                result.push(res);
            }
        }

        result
    }
}

fn dfs(curr: &String, target: &String, prod: f64, graph: &HashMap<String, Vec<(String, f64)>>, visited: &mut std::collections::HashSet<String>) -> f64 {
    if curr == target {
        return prod;
    }

    visited.insert(curr.clone());

    if let Some(neighbors) = graph.get(curr) {
        for (next, val) in neighbors {
            if !visited.contains(next) {
                let res = dfs(next, target, prod * val, graph, visited);
                if res != -1.0 {
                    return res;
                }
            }
        }
    }

    -1.0
}

struct Solution;

fn main() {
    println!("Solution");
}

Go

evaluate_division_dfs.go

package main
func solution() int { return 0 }

Approach 2: Union-Find

✓ Simple

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

evaluate_division_union-find.py

def calcEquation(equations, values, queries):
    parent = {}
    rank = {}

    def find(x):
        if x not in parent:
            parent[x] = x
            rank[x] = 0
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b, val):
        pa, pb = find(a), find(b)
        if pa == pb:
            return
        parent[pb] = pa
        rank[pa] = max(rank[pa], rank[pb] + 1)

    for (a, b), val in zip(equations, values):
        union(a, b, val)

    result = []
    for x, y in queries:
        if find(x) != find(y):
            result.append(-1.0)
        else:
            result.append(1.0)

    return result

C++

evaluate_division_union-find.cpp

#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, pair<string, double>> parent;

        for (int i = 0; i < equations.size(); i++) {
            unite(equations[i][0], equations[i][1], values[i], parent);
        }

        vector<double> result;
        for (const auto& query : queries) {
            string x = query[0], y = query[1];
            if (parent.find(x) == parent.end() || parent.find(y) == parent.end()) {
                result.push_back(-1.0);
            } else {
                auto [px, rx] = find(x, parent);
                auto [py, ry] = find(y, parent);
                if (px != py) {
                    result.push_back(-1.0);
                } else {
                    result.push_back(rx / ry);
                }
            }
        }
        return result;
    }

private:
    void unite(const string& a, const string& b, double val, unordered_map<string, pair<string, double>>& parent) {
        if (parent.find(a) == parent.end()) parent[a] = {a, 1.0};
        if (parent.find(b) == parent.end()) parent[b] = {b, 1.0};

        auto [pa, ra] = find(a, parent);
        auto [pb, rb] = find(b, parent);
        parent[pa] = {pb, val * rb / ra};
    }

    pair<string, double> find(const string& x, unordered_map<string, pair<string, double>>& parent) {
        if (parent[x].first != x) {
            auto [root, ratio] = find(parent[x].first, parent);
            parent[x].second *= ratio;
            parent[x].first = root;
        }
        return {parent[x].first, parent[x].second};
    }
};

Java

EvaluateDivisionUnion-Find.java

import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Double> ratio = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            union(a, b, values[i], parent, ratio);
        }

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String x = queries.get(i).get(0);
            String y = queries.get(i).get(1);
            if (!parent.containsKey(x) || !parent.containsKey(y) || !find(x, parent, ratio).equals(find(y, parent, ratio))) {
                result[i] = -1.0;
            } else {
                result[i] = ratio.get(x) / ratio.get(y);
            }
        }
        return result;
    }

    private void union(String a, String b, double val, Map<String, String> parent, Map<String, Double> ratio) {
        if (!parent.containsKey(a)) {
            parent.put(a, a);
            ratio.put(a, 1.0);
        }
        if (!parent.containsKey(b)) {
            parent.put(b, b);
            ratio.put(b, 1.0);
        }
        String pa = find(a, parent, ratio);
        String pb = find(b, parent, ratio);
        parent.put(pa, pb);
        ratio.put(pa, val * ratio.get(b) / ratio.get(a));
    }

    private String find(String x, Map<String, String> parent, Map<String, Double> ratio) {
        if (!parent.get(x).equals(x)) {
            String root = find(parent.get(x), parent, ratio);
            ratio.put(x, ratio.get(x) * ratio.get(parent.get(x)));
            parent.put(x, root);
        }
        return parent.get(x);
    }
}

JavaScript

evaluate_division_union-find.js

function solution() { return 0; }
module.exports = solution;

Rust

evaluate_division_union-find.rs

pub fn solution() -> i32 { 0 }

Go

evaluate_division_union-find.go

package main
func solution() int { return 0 }

Interview Tips

Key trade-offs to discuss

• Approach 1 vs Approach 2 trade-offs
• Edge cases and how to handle them
• Follow-up questions

← Previous
#130 Surrounded Regions Next
#207 Course Schedule →