How to Solve Evaluate Division

This problem can be solved by modeling equations as a weighted directed graph and performing depth-first search to answer queries. Each variable becomes a node, and each equation forms an edge with its division value. For queries that lack a connecting path or undefined variables, return -1.0; otherwise, multiply the weights along the traversal path to find the result.

Problem Statement

You are given a list of equations represented as variable pairs and a corresponding list of values such that equations[i] = [Ai, Bi] and values[i] = Ai / Bi. Each Ai and Bi is a string representing a single variable. Your task is to compute results for division queries based on these relationships.

Additionally, you are given a list of queries where each query is of the form [Cj, Dj], asking for the value of Cj / Dj. Return an array of answers where each element corresponds to the result of a query; if a query cannot be solved due to missing variables or disconnected components, return -1.0 for that query.

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]

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 ] note: x is undefined => -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]

Example details omitted.

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]

Example details omitted.

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.

Solution Approach

Model equations as a graph

Treat each variable as a graph node. For each equation Ai / Bi = value, add an edge from Ai to Bi with weight value and an edge from Bi to Ai with weight 1/value. This graph representation allows DFS to find paths representing multiplicative relationships.

Use depth-first search for queries

For each query [Cj, Dj], perform DFS starting from Cj to Dj, multiplying edge weights along the path. If DFS reaches Dj, return the product of weights; if not, return -1.0. Track visited nodes to avoid cycles and infinite recursion.

Handle edge cases

Directly return 1.0 for queries where Cj equals Dj and Cj exists in the graph. Return -1.0 if either variable is missing. This ensures correctness for self-division and undefined variable cases, which are common pitfalls in graph-based division problems.

Complexity Analysis

Time complexity depends on DFS traversal for each query, potentially visiting all connected nodes, leading to O(Q * N) where Q is number of queries and N is number of variables. Space complexity includes graph storage and visited set, O(N + E) where E is number of edges.

What Interviewers Usually Probe

• Do you recognize that each variable can be represented as a node in a graph?
• Could you use DFS to traverse paths and multiply values along edges?
• How do you handle queries with variables not present in any equation?

Common Pitfalls or Variants

Common pitfalls

• Forgetting to add the inverse edge 1/value, which breaks paths in DFS.
• Not tracking visited nodes, causing infinite loops in cyclic graphs.
• Returning incorrect values for self-division or undefined variables.

Follow-up variants

• Solve using BFS instead of DFS for each query to find shortest multiplicative path.
• Use Union-Find with weighted edges to precompute connected component ratios.
• Handle large datasets with memoization to cache intermediate division results.

How GhostInterview Helps

• GhostInterview identifies graph traversal patterns and recommends DFS for evaluating division chains.
• It flags missing nodes and cycle pitfalls, ensuring correct -1.0 returns where applicable.
• Provides guided steps to model variables as nodes and equations as weighted edges for fast query answers.

Topic Pages

• Array
• String
• Depth-First Search
• Breadth-First Search
• Union Find
• Graph
• Shortest Path

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the core pattern in Evaluate Division?

The problem follows a graph traversal pattern where variables are nodes and equations form weighted edges.

How do I handle queries where variables are not connected?

Return -1.0 when DFS or BFS cannot find a path between the variables in the graph.

Can I optimize repeated queries?

Yes, caching previously computed ratios or using Union-Find can reduce redundant traversal computations.

Why do we need inverse edges in the graph?

Without adding the inverse edges, DFS cannot traverse in the opposite direction to compute values like Bi / Ai.

Is DFS always better than BFS for this problem?

DFS is suitable for depth-oriented searches in small graphs, but BFS can be used to guarantee shortest path traversal; choice depends on graph size and query frequency.