#399

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Evaluate Division

Compute the results of division queries from given equations using graph traversal and depth-first search efficiently.

array string depth first search breadth first search union find

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[float], queries: List[List[str]]
    ) -> List[float]:
        def find(x):
            if p[x] != x:
                origin = p[x]
                p[x] = find(p[x])
                w[x] *= w[origin]
            return p[x]

        w = defaultdict(lambda: 1)
        p = defaultdict()
        for a, b in equations:
            p[a], p[b] = a, b
        for i, v in enumerate(values):
            a, b = equations[i]
            pa, pb = find(a), find(b)
            if pa == pb:
                continue
            p[pa] = pb
            w[pa] = w[b] * v / w[a]
        return [
            -1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d]
            for c, d in queries
        ]

Continue Practicing

#721 accounts merge #839 similar string groups #924 minimize malware spread