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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Evaluate Division and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →