Evaluate Division - LeetCode75 Python Solution Explained

The Evaluate Division problem (LeetCode75) is a graph traversal problem that tests your understanding of DFS, graph construction, and variable relationships. It is frequently asked in coding interviews to assess your skills in graph representation and query evaluation.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given a list of equations equations[i] = [Ai, Bi] and their corresponding values values[i] = Ai / Bi. You are also given some queries queries[j] = [Cj, Dj].

Return the results of the queries. If the division is undefined, return -1.0.

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.0,0.5,-1.0,1.0,-1.0]

Explanation:

a / c = a / b * b / c = 2 * 3 = 6.0
b / a = 1 / (a / b) = 0.5
a / e = -1.0 (undefined)
a / a = 1.0
x / x = -1.0 (undefined variable)

Example 2

Input:

equations = [["x1","x2"],["x2","x3"],["x3","x4"],["x4","x5"]]
values = [3.0,4.0,5.0,6.0]
queries = [["x1","x5"],["x5","x2"],["x2","x4"],["x2","x2"],["x2","x9"],["x9","x9"]]

Output:

[360.0,0.0083333,20.0,1.0,-1.0,-1.0]

Complete Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(dict)

        # Build the graph
        for (numerator, denominator), value in zip(equations, values):
            graph[numerator][denominator] = value
            graph[denominator][numerator] = 1 / value  # Add the reverse edge

        def dfs(start, end, visited):
            if start not in graph or end not in graph:
                return -1.0  # Undefined variable

            if start == end:
                return 1.0  # Variable divided by itself

            visited.add(start)

            for neighbor, value in graph[start].items():
                if neighbor not in visited:
                    result = dfs(neighbor, end, visited)
                    if result != -1.0:
                        return value * result

            return -1.0

        results = []
        for query in queries:
            start, end = query
            visited = set()
            result = dfs(start, end, visited)
            results.append(result)

        return results

Step-by-Step Explanation

Step 1: Build a Graph

We represent variables as nodes and divisions as edges with weights.

graph = defaultdict(dict)
for (numerator, denominator), value in zip(equations, values):
    graph[numerator][denominator] = value
    graph[denominator][numerator] = 1 / value

a / b = 2.0 → graph[a][b] = 2.0, graph[b][a] = 0.5

Step 2: Define DFS Function

We traverse the graph recursively to find a path from start to end.

def dfs(start, end, visited):
    if start not in graph or end not in graph:
        return -1.0
    if start == end:
        return 1.0
    visited.add(start)
    for neighbor, value in graph[start].items():
        if neighbor not in visited:
            result = dfs(neighbor, end, visited)
            if result != -1.0:
                return value * result
    return -1.0

Return 1.0 if the same variable.
Return -1.0 if variable does not exist.
Multiply edge weights along the path to compute the division.

Step 3: Evaluate Queries

For each query, perform DFS and store the result.

results = []
for query in queries:
    start, end = query
    visited = set()
    result = dfs(start, end, visited)
    results.append(result)

Time and Space Complexity

Time Complexity:O(Q * (V + E))
- Q = number of queries
- V = number of variables
- E = number of edges (equations)
Space Complexity:O(V + E)
- Graph storage and recursion stack for DFS.

Edge Cases

Query contains a variable not in equations: return -1.0
Variable divided by itself: return 1.0
Disconnected graph components: return -1.0 if no path exists

Real-World Applications

Currency Exchange: Evaluate conversion rates between currencies.
Chemical Reactions: Compute relative concentrations of compounds.
Unit Conversions: Convert between units when direct formulas are unavailable.
Dependency Ratios: Calculate ratios in hierarchical or networked data structures.

Conclusion

The Evaluate Division problem is an excellent exercise in graph modeling, DFS traversal and path-based computation. By constructing a weighted graph and traversing it recursively, we can compute any variable division efficiently even for indirect connections.

This problem strengthens your skills in DFS, graph representation and recursion which are highly relevant in interviews and real-world applications involving networks, ratios and conversions.

Evaluate Division – LeetCode75 Python Solution Explained