LeetCode 399 - Evaluate Division

LeetCode Problem 399

Difficulty: 🟡 Medium
Topics: Array, String, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Shortest Path

Solution

Problem Understanding

This problem gives us a collection of equations between variables, where each equation represents a division relationship. For example, if we are given:

a / b = 2.0
b / c = 3.0

then we can infer additional relationships such as:

a / c = 6.0
c / a = 1 / 6.0

The task is to answer multiple queries of the form:

x / y = ?

For every query, we must determine whether a valid division value can be derived from the known equations. If it can, we return the computed value. If it cannot, we return -1.0.

The important observation is that the equations form relationships between variables, which naturally creates a graph structure. Each variable can be treated as a node, and each equation creates a weighted edge between two nodes.

For example:

a / b = 2.0

creates:

a -> b with weight 2.0
b -> a with weight 0.5

The reciprocal edge exists because:

b / a = 1 / 2.0

The input consists of three arrays:

• equations, where each entry contains two variables
• values, where each entry contains the corresponding division result
• queries, where each entry asks for a division result

The output is an array of floating point values, one for each query.

The constraints are relatively small:

• At most 20 equations
• At most 20 queries

This means even graph traversal approaches such as DFS or BFS are efficient enough. We do not need highly optimized shortest path algorithms.

Several edge cases are important:

• A query may contain variables that never appeared in any equation
• A query may ask for division by itself, such as a / a
• Two variables may belong to disconnected components
• The answer may require traversing multiple intermediate variables

The problem guarantees:

• No contradictions exist
• Division by zero will never occur
• Inputs are always valid

These guarantees simplify the implementation because we do not need to handle inconsistent equations.

Approaches

Brute Force Approach

A naive brute force solution would attempt to recompute relationships from scratch for every query.

For each query:

1. Try every possible path between the numerator and denominator
2. Multiply ratios along the path
3. Return the result if a valid path exists

This can be implemented using recursive backtracking without explicitly building an adjacency list. For every equation, we would repeatedly scan the entire equations array to find usable connections.

This approach is correct because eventually every reachable path is explored. If a valid chain of equations exists, the algorithm will discover it.

However, this is inefficient because:

• Every query repeatedly scans all equations
• The same subproblems are recomputed many times
• Graph connectivity is not stored efficiently

Even though constraints are small here, this approach does not scale well conceptually.

Optimal Approach

The better solution models the equations as a weighted graph.

Each variable becomes a node.

Each equation:

a / b = k

creates two directed edges:

a -> b with weight k
b -> a with weight 1 / k

To answer a query:

x / y

we perform DFS or BFS from x to y.

As we traverse edges, we multiply edge weights together. The product represents the accumulated ratio from the starting variable to the current variable.

For example:

a -> b = 2
b -> c = 3

Traversing:

a -> b -> c

produces:

2 * 3 = 6

which means:

a / c = 6

This works because multiplication of ratios composes naturally along graph paths.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(Q × E²)	O(E)	Repeatedly scans equations for every query
Optimal	O(E + Q × (V + E))	O(V + E)	Uses weighted graph with DFS/BFS traversal

Where:

• Q = number of queries
• V = number of variables
• E = number of equations

Algorithm Walkthrough

Step 1: Build the Graph

Create an adjacency list where each variable maps to neighboring variables and edge weights.

For every equation:

A / B = value

insert:

A -> (B, value)
B -> (A, 1/value)

This allows traversal in both directions.

Example:

a / b = 2

becomes:

graph["a"].append(("b", 2.0))
graph["b"].append(("a", 0.5))

Step 2: Process Each Query

For every query [start, end]:

• If either variable does not exist in the graph, return -1.0
• If start == end, return 1.0
• Otherwise, run DFS or BFS

Step 3: Perform DFS Traversal

The DFS function keeps track of:

• Current node
• Current accumulated product
• Visited nodes

At every step:

1. If current node equals target, return accumulated product
2. Mark current node as visited
3. Explore neighbors
4. Multiply current product by edge weight
5. Continue recursively

Example traversal:

a -> b = 2
b -> c = 3

DFS progression:

Start at a with product 1
Move to b, product = 1 * 2 = 2
Move to c, product = 2 * 3 = 6

Return 6.

Step 4: Handle Unreachable Nodes

If DFS finishes without reaching the target, return -1.0.

This means no valid relationship exists between the variables.

Why it works

The graph stores all known division relationships. Every path between two variables represents a valid chain of multiplicative ratios. Because division relationships compose multiplicatively, multiplying edge weights along a path produces the correct final ratio. DFS explores all reachable paths, so if a valid relationship exists, the algorithm will find it.

Python Solution

from collections import defaultdict
from typing import List, Set

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

        graph = defaultdict(list)

        # Build weighted graph
        for (numerator, denominator), value in zip(equations, values):
            graph[numerator].append((denominator, value))
            graph[denominator].append((numerator, 1.0 / value))

        def dfs(
            current: str,
            target: str,
            current_product: float,
            visited: Set[str]
        ) -> float:

            if current == target:
                return current_product

            visited.add(current)

            for neighbor, weight in graph[current]:
                if neighbor in visited:
                    continue

                result = dfs(
                    neighbor,
                    target,
                    current_product * weight,
                    visited
                )

                if result != -1.0:
                    return result

            return -1.0

        answers = []

        for start, end in queries:

            if start not in graph or end not in graph:
                answers.append(-1.0)

            elif start == end:
                answers.append(1.0)

            else:
                visited = set()
                answers.append(dfs(start, end, 1.0, visited))

        return answers

The implementation begins by constructing a weighted adjacency list using defaultdict(list). Each equation contributes two directed edges, one for the original ratio and one for the reciprocal ratio.

The DFS helper function recursively searches for a path between two variables. The current_product parameter stores the multiplication of all edge weights encountered so far. Once the target node is reached, this accumulated product represents the final answer.

The visited set prevents cycles from causing infinite recursion. Since graph traversal may revisit variables through reciprocal edges, cycle prevention is essential.

The main query loop handles edge cases before running DFS. Undefined variables immediately return -1.0, while identical variables return 1.0 as long as the variable exists in the graph.

Go Solution

package main

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	graph := make(map[string][][]interface{})

	// Build graph
	for i, equation := range equations {
		a := equation[0]
		b := equation[1]
		value := values[i]

		graph[a] = append(graph[a], []interface{}{b, value})
		graph[b] = append(graph[b], []interface{}{a, 1.0 / value})
	}

	var dfs func(
		current string,
		target string,
		product float64,
		visited map[string]bool,
	) float64

	dfs = func(
		current string,
		target string,
		product float64,
		visited map[string]bool,
	) float64 {

		if current == target {
			return product
		}

		visited[current] = true

		for _, neighborInfo := range graph[current] {
			neighbor := neighborInfo[0].(string)
			weight := neighborInfo[1].(float64)

			if visited[neighbor] {
				continue
			}

			result := dfs(
				neighbor,
				target,
				product*weight,
				visited,
			)

			if result != -1.0 {
				return result
			}
		}

		return -1.0
	}

	results := make([]float64, 0, len(queries))

	for _, query := range queries {
		start := query[0]
		end := query[1]

		_, startExists := graph[start]
		_, endExists := graph[end]

		if !startExists || !endExists {
			results = append(results, -1.0)
			continue
		}

		if start == end {
			results = append(results, 1.0)
			continue
		}

		visited := make(map[string]bool)

		result := dfs(start, end, 1.0, visited)
		results = append(results, result)
	}

	return results
}

The Go implementation follows the same logic as the Python version. One notable difference is that Go does not support heterogeneous tuples directly, so the adjacency list uses [][]interface{} to store neighbor and weight pairs.

Maps in Go naturally support existence checks using the two-value assignment pattern:

value, exists := map[key]

The DFS function is implemented as a recursive closure assigned to a variable.

Go slices are dynamically resized similarly to Python lists, so appending results is straightforward.

Worked 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"]]

Graph Construction

From	To	Weight
a	b	2.0
b	a	0.5
b	c	3.0
c	b	0.3333

Graph:

a -> b (2.0)
b -> a (0.5), c (3.0)
c -> b (0.3333)

Query: a / c

DFS traversal:

Current Node	Product
a	1.0
b	2.0
c	6.0

Answer:

6.0

Query: b / a

Traversal:

Current Node	Product
b	1.0
a	0.5

Answer:

0.5

Query: a / e

Variable e does not exist in graph.

Answer:

-1.0

Query: a / a

Same variable, and variable exists.

Answer:

1.0

Query: x / x

Variable x does not exist.

Answer:

-1.0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E + Q × (V + E))	Build graph once, DFS per query
Space	O(V + E)	Graph storage and visited set

The graph construction phase processes each equation exactly once, producing two directed edges per equation.

For every query, DFS may visit every variable and edge in the worst case. Since the graph is small, this traversal remains efficient.

The space complexity comes primarily from the adjacency list and the recursion stack used during DFS.

Test Cases

from typing import List

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

        from collections import defaultdict

        graph = defaultdict(list)

        for (a, b), value in zip(equations, values):
            graph[a].append((b, value))
            graph[b].append((a, 1.0 / value))

        def dfs(current, target, product, visited):
            if current == target:
                return product

            visited.add(current)

            for neighbor, weight in graph[current]:
                if neighbor not in visited:
                    result = dfs(
                        neighbor,
                        target,
                        product * weight,
                        visited
                    )

                    if result != -1.0:
                        return result

            return -1.0

        answers = []

        for start, end in queries:

            if start not in graph or end not in graph:
                answers.append(-1.0)

            elif start == end:
                answers.append(1.0)

            else:
                answers.append(
                    dfs(start, end, 1.0, set())
                )

        return answers

solution = Solution()

# Example 1
assert solution.calcEquation(
    [["a", "b"], ["b", "c"]],
    [2.0, 3.0],
    [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
) == [6.0, 0.5, -1.0, 1.0, -1.0]  # basic chain and undefined variable

# Example 2
assert solution.calcEquation(
    [["a", "b"], ["b", "c"], ["bc", "cd"]],
    [1.5, 2.5, 5.0],
    [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]
) == [3.75, 0.4, 5.0, 0.2]  # multiple connected components

# Example 3
assert solution.calcEquation(
    [["a", "b"]],
    [0.5],
    [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]
) == [0.5, 2.0, -1.0, -1.0]  # reciprocal and undefined variables

# Self division existing variable
assert solution.calcEquation(
    [["a", "b"]],
    [2.0],
    [["a", "a"]]
) == [1.0]  # variable divided by itself

# Disconnected graph
assert solution.calcEquation(
    [["a", "b"], ["c", "d"]],
    [2.0, 3.0],
    [["a", "d"]]
) == [-1.0]  # no path between components

# Longer chain
assert solution.calcEquation(
    [["a", "b"], ["b", "c"], ["c", "d"]],
    [2.0, 3.0, 4.0],
    [["a", "d"]]
) == [24.0]  # multiplication across long path

# Reverse traversal
assert solution.calcEquation(
    [["a", "b"], ["b", "c"]],
    [2.0, 4.0],
    [["c", "a"]]
) == [0.125]  # reciprocal traversal

# Undefined variables
assert solution.calcEquation(
    [["a", "b"]],
    [2.0],
    [["x", "x"], ["a", "x"]]
) == [-1.0, -1.0]  # variables absent from graph

print("All test cases passed.")

Test	Why
Basic chain conversion	Verifies multi-step multiplication
Reciprocal query	Verifies reverse edges
Undefined variable	Ensures missing nodes return -1.0
Self division	Ensures a / a = 1.0
Disconnected graph	Ensures unreachable nodes return -1.0
Long chain	Verifies repeated multiplication
Reverse traversal	Confirms reciprocal edge correctness
Multiple components	Ensures traversal stays within component

Edge Cases

Undefined Variables

A query may reference variables that never appeared in any equation.

Example:

equations = [["a","b"]]
query = ["x","y"]

A naive implementation might incorrectly return 1.0 for x / x, but the problem explicitly states undefined variables cannot be evaluated.

The implementation handles this by checking graph membership before DFS begins.

Self Division

Queries such as:

a / a

should return 1.0 if a exists in the graph.

This case can easily be mishandled if the algorithm only searches for paths between different nodes. The implementation explicitly checks:

elif start == end:
    answers.append(1.0)

before DFS execution.

Disconnected Components

Variables may exist in separate connected components.

Example:

a / b = 2
c / d = 3

There is no relationship between a and d.

Without proper traversal termination, a buggy implementation might accidentally produce invalid results. The DFS correctly returns -1.0 when no path reaches the target.

Cycles in the Graph

Because reciprocal edges are added automatically, cycles naturally appear.

Example:

a -> b
b -> a

Without a visited set, DFS would recurse infinitely.

The implementation prevents this by storing visited nodes during traversal and skipping already explored variables.