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 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 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

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →