Evaluate Division

Difficulty: Medium Source: NeetCode

Problem

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]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the j-th query where you must find the result of Cj / Dj.

Return the results of all queries. If the answer to a query does not exist, return -1.0.

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.0, 0.5, -1.0, 1.0, -1.0]

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values[i] > 0.0
• 1 <= queries.length <= 20

Prerequisites

Before attempting this problem, you should be comfortable with:

• Weighted directed graphs — edges have a value (the division result)
• BFS / DFS for path finding — multiplying weights along a path gives the query answer
• Graph modeling — translating a math problem into a graph traversal

1. BFS for Each Query

Intuition

Model the variables as nodes and the equations as directed weighted edges. If a / b = 2, add edges a → b with weight 2.0 and b → a with weight 1/2.0 = 0.5. To answer a / c, find a path from a to c and multiply all edge weights along the path. BFS is perfect for this since any path gives the correct answer (the graph is consistent).

Algorithm

1. Build a weighted adjacency list from equations and values.
2. For each query (src, dst):
   • If either is unknown, return -1.0.
   • If src == dst, return 1.0.
   • BFS from src, tracking the accumulated product. Stop when dst is found.
3. Return -1.0 if dst is unreachable.

Solution

from collections import defaultdict, deque

def calcEquation(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, dst):
        if src not in graph or dst not in graph:
            return -1.0
        if src == dst:
            return 1.0
        visited = {src}
        queue = deque([(src, 1.0)])
        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]


equations = [["a","b"],["b","c"]]
values = [2.0, 3.0]
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
print(calcEquation(equations, values, queries))
# [6.0, 0.5, -1.0, 1.0, -1.0]

Complexity

• Time: O(Q * (V + E)) where Q = queries, V = unique variables, E = equations
• Space: O(V + E) for the graph

2. Floyd-Warshall on Division

Intuition

If we know a/b and b/c, we can compute a/c = (a/b) * (b/c). This is exactly the Floyd-Warshall transitive closure idea applied to multiplicative ratios. Precompute all pairwise division results using three nested loops, then answer each query in O(1).

Algorithm

1. Initialize dist[a][b] = val for each equation, dist[a][a] = 1.0 for all known variables, dist[b][a] = 1/val.
2. For each intermediate k, for each i, for each j: if dist[i][k] and dist[k][j] are known, set dist[i][j] = dist[i][k] * dist[k][j].
3. Answer each query with dist[src][dst] or -1.0 if unknown.

Solution

from collections import defaultdict

def calcEquation(equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
    # Collect all unique variables
    variables = set()
    for a, b in equations:
        variables.add(a)
        variables.add(b)

    # Initialize ratio table
    ratio = defaultdict(dict)
    for var in variables:
        ratio[var][var] = 1.0

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

    # Floyd-Warshall: compute transitive ratios
    for k in variables:
        for i in variables:
            for j in variables:
                if k in ratio[i] and j in ratio[k]:
                    ratio[i][j] = ratio[i][k] * ratio[k][j]

    result = []
    for src, dst in queries:
        if src not in ratio or dst not in ratio[src]:
            result.append(-1.0)
        else:
            result.append(ratio[src][dst])
    return result


equations = [["a","b"],["b","c"]]
values = [2.0, 3.0]
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
print(calcEquation(equations, values, queries))
# [6.0, 0.5, -1.0, 1.0, -1.0]

Complexity

• Time: O(V³ + Q) — V³ for Floyd-Warshall, Q for queries
• Space: O(V²) for the ratio table

Common Pitfalls

Unknown variables in queries. If src or dst doesn’t appear in any equation, return -1.0. Check src not in graph before doing any traversal.

Self-queries. a / a = 1.0 if a is a known variable. But x / x = -1.0 if x is never mentioned in equations — it’s unknown, not 1.0.

Adding reverse edges. For each equation a / b = k, add both graph[a][b] = k and graph[b][a] = 1/k. Without reverse edges, many queries will fail even when the answer is computable.