Skip to main content

399. Evaluate Division

medium

Given division equations like a / b = 2.0 and b / c = 3.0, evaluate query divisions like a / c. A graph problem hiding in math notation: nodes are variables, edges are ratios. Solve with DFS/BFS or Union-Find with rank.

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 j-th 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. Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

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: Given: a / b = 2.0, b / c = 3.0; queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?; return: [6.0, 0.5, -1.0, 1.0, -1.0].

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]

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

Model as a weighted directed graph. Each equation A / B = v creates an edge A -> B with weight v and an edge B -> A with weight 1 / v.

Hint 2

A query C / D = ? is a path search from C to D. Multiply edge weights along the path.

Hint 3

DFS or BFS from C, tracking the product along the current path. Return the first time you reach D, or -1 if no path exists.

Hint 4

Special cases: if either variable isn't in the graph, return -1. If C == D and is in the graph, return 1. Union-Find with weighted ratios is the more advanced variant.

Solution approach

Reveal approach

Build a weighted directed graph from the equations: for each A / B = v add edges A -> B (weight v) and B -> A (weight 1 / v). For each query (C, D): if C or D is missing from the graph, return -1. If C == D and C is in the graph, return 1. Else DFS or BFS from C, multiplying weights along the path, looking for D — return the accumulated product on success or -1 on failure. Track visited nodes to avoid cycles. O(N + Q * (N + E)) time where N is variables, E is equations, Q is queries — fast enough for the given bounds. The Union-Find variant maintains a parent pointer plus a multiplicative ratio to root; queries become near-O(1) with path compression but require more careful weight propagation.

Complexity

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

Related patterns

  • graph
  • dfs
  • bfs
  • union-find
  • math

Related problems

Asked at

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

  • Google
  • Amazon
  • Apple
  • Bloomberg

More Math practice problems

See all Math problems →