Skip to main content

399. Evaluate Division

medium

Given equations a/b = k as edges, answer queries x/y by chaining ratios. Treat variables as nodes and ratios as weighted edges — a DFS multiplying edge weights along the path produces the answer.

By Sam K., Founder, InterviewChamp.AI · Last verified

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 jth query where you must find the answer for Cj / Dj = ?. Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Constraints

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj consist of lower case English letters and digits.

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]

Explanation: a/b = 2, b/c = 3, so a/c = 6, b/a = 1/2, a/e doesn't exist, a/a = 1, x/x doesn't exist.

Example 2

Input
equations = [['a','b'],['b','c'],['bc','cd']], values = [1.5,2.5,5.0], queries = [['a','c'],['c','b'],['bc','cd'],['cd','bc']]
Output
[3.75000,0.40000,5.00000,0.20000]

Example 3

Input
equations = [['a','b']], values = [0.5], queries = [['a','b'],['b','a'],['a','c'],['x','y']]
Output
[0.50000,2.00000,-1.00000,-1.00000]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Treat variables as nodes; each equation a/b = k gives an edge a -> b with weight k AND b -> a with weight 1/k.

Hint 2

To answer query x/y, run DFS from x to y; multiply edge weights along the path. If unreachable, return -1.

Hint 3

Track visited nodes to avoid revisits, but reset visited between queries.

Solution approach

Reveal approach

Build a graph: for each equation (a, b, v), add edge a -> b with weight v and b -> a with weight 1/v. For each query (x, y): if x or y is missing from the graph, return -1. If x == y, return 1.0. Otherwise DFS from x with current product = 1.0 and a visited set. At node u, iterate (v, w) neighbors; if v == y return product * w; else if v not in visited, recurse with product * w and visited += {v}, returning early if a recursive call returns a non-(-1) value. If exhausted, return -1. The DFS is the classic graph-as-weighted-multiplier traversal. O(Q * (V + E)) total for Q queries. Union-Find-by-weight is a more advanced alternative that does each query in near-O(1) after the merge phase.

Complexity

Time
O(Q * (V + E))
Space
O(V + E)

Related patterns

  • dfs
  • bfs
  • union-find
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Uber
  • Bloomberg

More Graphs practice problems

See all Graphs problems →