Evaluate Division

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonGoogleMicrosoftMeta

Problem Description

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].

Given some queries, where queries[j] = [Cj, Dj], return the answers to all queries. If the answer does not exist, return -1.0.

Examples

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]

Constraints

1 ≤ equations.length ≤ 20
equations[i].length == 2
1 ≤ Ai.length, Bi.length ≤ 5
values[i] != 0.0

Build a Weighted Directed Graph

Model each variable as a node. For equation A / B = k, add directed edge A -> B with weight k and reverse edge B -> A with weight 1/k. To evaluate C / D, find a path from C to D in the graph and multiply edge weights along the path.

BFS or DFS from the source variable, tracking the accumulated product. If the destination is reached, return the product. If it’s unreachable, return -1.0.

Solution: BFS on Weighted Graph

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<>();

        // build weighted bidirectional graph
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            double val = values[i];
            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, val);
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / val);
        }

        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String src = queries.get(i).get(0), dst = queries.get(i).get(1);
            if (!graph.containsKey(src) || !graph.containsKey(dst)) {
                results[i] = -1.0;
            } else {
                results[i] = bfs(graph, src, dst);
            }
        }
        return results;
    }

    private double bfs(Map<String, Map<String, Double>> graph, String src, String dst) {
        if (src.equals(dst)) return 1.0;
        Queue<Object[]> queue = new LinkedList<>(); // [node, product]
        Set<String> visited = new HashSet<>();
        queue.offer(new Object[]{src, 1.0});
        visited.add(src);

        while (!queue.isEmpty()) {
            Object[] curr = queue.poll();
            String node = (String) curr[0];
            double product = (double) curr[1];

            for (Map.Entry<String, Double> neighbor : graph.get(node).entrySet()) {
                String next = neighbor.getKey();
                double weight = neighbor.getValue();
                if (next.equals(dst)) return product * weight;
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.offer(new Object[]{next, product * weight});
                }
            }
        }
        return -1.0;
    }
}

from collections import defaultdict, deque

class Solution:
    def calcEquation(self, equations: list[list[str]], values: list[float],
                     queries: list[list[str]]) -> list[float]:
        graph = defaultdict(dict)

        for (a, b), val in zip(equations, values):
            graph[a][b] = val
            graph[b][a] = 1.0 / val

        def bfs(src: str, dst: str) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0

            queue = deque([(src, 1.0)])
            visited = {src}

            while queue:
                node, product = queue.popleft()
                for neighbor, weight in graph[node].items():
                    if neighbor == dst:
                        return product * weight
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, product * weight))

            return -1.0

        return [bfs(src, dst) for src, dst in queries]

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>

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

        for (int i = 0; i < (int)equations.size(); i++) {
            auto& a = equations[i][0]; auto& b = equations[i][1];
            graph[a][b] = values[i];
            graph[b][a] = 1.0 / values[i];
        }

        std::vector<double> results;
        for (auto& q : queries) {
            results.push_back(bfs(graph, q[0], q[1]));
        }
        return results;
    }

private:
    double bfs(std::unordered_map<std::string, std::unordered_map<std::string, double>>& graph,
               const std::string& src, const std::string& dst) {
        if (!graph.count(src) || !graph.count(dst)) return -1.0;
        if (src == dst) return 1.0;

        std::queue<std::pair<std::string, double>> q;
        std::unordered_set<std::string> visited;
        q.push({src, 1.0});
        visited.insert(src);

        while (!q.empty()) {
            auto [node, product] = q.front(); q.pop();
            for (auto& [neighbor, weight] : graph[node]) {
                if (neighbor == dst) return product * weight;
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push({neighbor, product * weight});
                }
            }
        }
        return -1.0;
    }
};

Complexity Analysis:

Time Complexity: O(Q * (V + E)) where Q is queries, V is variables, E is equations. For each query, BFS traverses the graph.
Space Complexity: O(V + E) for the graph.

Where it breaks: if src == dst, always return 1.0 (a variable divided by itself is 1), even if the variable doesn’t appear in equations. The constraint says to return -1.0 if the variable doesn’t exist in the graph at all (which is handled by the first check).

Common Mistakes

Returning 1.0 for same-variable queries without checking if the variable exists in the graph. Query ["x", "x"] where x doesn’t appear in any equation should return -1.0.
Not adding reverse edges. If A / B = 2, you need B / A = 0.5 explicitly. BFS only traverses directed edges.