Medium

Evaluate Division

051

Given equations encoded as variable pairs, values, and queries, return each query result.

EXAMPLES

Example 1

Input
{
  "equations": [
    [
      0,
      1
    ],
    [
      1,
      2
    ]
  ],
  "names": [
    "a",
    "b",
    "c"
  ],
  "values": [
    2,
    3
  ],
  "queries": [
    [
      0,
      2
    ],
    [
      1,
      0
    ],
    [
      0,
      3
    ]
  ]
}

Output
[
  6,
  0.5,
  -1
]

FUNCTION SHAPE

equations: intMatrixnames: stringArrayvalues: intArrayqueries: intMatrix→doubleArray

SOLUTION NOTE

We run a BFS/DFS for each query, where each node in the graph represents a variable, and a directed edge from A -> B has weight A / B. With this construction, we have that a path from A to B to C represents: A / C = (A / B) * (B / C), WHEN we multiply the edges together!

Just make sure that A -> B has weight values[i], and so B -> A has weight 1 / values[i]. We can use any graph traversal algorithm to find a path from X to Y. Try to compare the bfs and dfs solutions!

Reveal reference solution +

pythonREFERENCE

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

    # Build the graph
    for (a, b), val in zip(equations, values):
        graph[a].append((b, val))
        graph[b].append((a, 1 / val))

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

        queue = deque([(start, 1.0)])
        visited = set()

        while queue:
            node, curr_product = queue.popleft()
            if node == end: return curr_product
            if node in visited: continue
            visited.add(node)
            for neighbor, value in graph[node]:
                new_product = curr_product * value
                queue.append((neighbor, new_product))

        return -1.0

    # Process all queries
    return [bfs(x, y) for x, y in queries]

# DFS Solution
def calcEquation(self, equations, values, queries):
    graph = defaultdict(dict)

    # Step 1: Build the graph
    for (a, b), val in zip(equations, values):
        graph[a][b] = val
        graph[b][a] = 1 / 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].items():
            if neighbor in visited: continue
            res = dfs(neighbor, end, visited)
            if res != -1.0:
                return weight * res
        return -1.0

    # Step 2: Evaluate each query
    result = []
    for x, y in queries:
        result.append(dfs(x, y, set()))
    return result

TimeO(Q * (V + E))

SpaceO(V + E)

Open on LeetCode ↗