Skip to main content
Talentd

Evaluate Division - Solution & Explanation

MediumArrayStringDepth-First SearchBreadth-First Search14 min readAsked at: Amazon, Microsoft, Apple +20
Practice this problem

Problem Statement

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

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

 

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

 

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.

Approach Overview

Problem Overview: You receive equations like a / b = 2.0 and must answer queries such as a / c. If the relationships exist through other variables, compute the result using those connections. If no path exists between two variables, return -1.0.

Approach 1: Graph Representation and DFS/BFS (Time: O(Q * (V + E)), Space: O(V + E))

Model the equations as a weighted graph. Each variable becomes a node, and every equation a / b = k creates two edges: a → b with weight k and b → a with weight 1/k. To answer a query like x / y, run a Depth-First Search or Breadth-First Search starting from x. Multiply edge weights along the path until you reach y. If a path exists, the product of weights gives the answer; otherwise return -1.0.

This approach works because ratios compose multiplicatively along paths in the graph. During traversal, maintain a visited set to avoid cycles. DFS is commonly used because the graph is usually small, but BFS works equally well. Building the adjacency list takes O(E) time where E is the number of equations, and each query may traverse the graph once.

Problems like this are classic graph traversal tasks and commonly appear alongside Depth-First Search interview questions.

Approach 2: Union-Find with Path Compression (Time: ~O((E + Q) α(N)), Space: O(N))

Another approach treats each variable as part of a disjoint set. Instead of storing only connectivity, store a weight representing the ratio between a node and its parent. When processing an equation a / b = k, union the sets while preserving the ratio relationship. The parent links maintain multiplicative weights so any node can compute its value relative to the set root.

When answering a query x / y, check whether both variables share the same root. If they do, compute the ratio using their stored weights relative to that root. If they belong to different sets, the relationship is undefined and the answer is -1.0. Path compression keeps the structure shallow and maintains correct weight adjustments.

This weighted Union-Find technique is common in problems involving relative relationships or ratios. It combines Union-Find with algebraic weight propagation to answer queries efficiently.

Recommended for interviews: Start with the graph + DFS explanation because it directly models the problem and demonstrates strong understanding of graph traversal. Many candidates implement this first. The Union-Find approach is more advanced and often viewed as the optimized design because it handles multiple queries efficiently with near-constant time operations.

Approach 1: Graph Representation and DFS

Approach: Represent the given variable equations as a graph. Each variable is a node, and an equation between two variables becomes a directed edge with a weight from one node to another representing the ratio. To find the result of a query, search for a path from the dividend node to the divisor node using Depth First Search (DFS). If a path is found, multiply the weights along the path to get the result. If no path is found, return -1.0 as the result cannot be determined.

The Python implementation uses a recursive DFS function to find a path from the start variable to the end variable. The graph is built using a dictionary of dictionaries, allowing easy access to directly connected nodes and the associated division value. If a direct or indirect path exists, the function calculates the result by multiplying the weights along the path. If no path can be found, it returns -1.0.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(V + E) for each query, where V is the number of variables and E is the number of equations due to the DFS traversal. Overall complexity is O(Q * (V + E)) for Q queries.
Space Complexity: O(V + E) for storing the graph.

Try this approach in the editor →

Approach 2: Union-Find with Path Compression

Approach: Use Union-Find (Disjoint Set Union, DSU) with path compression to represent connected components of variables where each component can efficiently find the "parent" or representative of a set. Each variable is associated with a weight that represents its relative scale with respect to its parent. This method efficiently handles union operations and queries to determine the result by finding the root of each variable and combining their scales.

This C++ solution uses a Union-Find data structure with path compression. For each equation, it unifies the variables into a single component, maintaining their relative ratios. For each query, it determines whether the variables are in the same component and calculates the result using the stored weights (which represent ratios to their respective roots).

Code

C++Java

C++

Java

Complexity

Time Complexity: O(E + Q * α(V)), where E is the number of equations, Q is the number of queries, V is the number of variables, and α is the inverse Ackermann function, which grows very slowly.
Space Complexity: O(V) for storing parent information and weights.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoRustTypeScript

Python

Java

C++

Go

Rust

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Graph Representation and DFS

Time Complexity: O(V + E) for each query, where V is the number of variables and E is the number of equations due to the DFS traversal. Overall complexity is O(Q * (V + E)) for Q queries.
Space Complexity: O(V + E) for storing the graph.

Union-Find with Path Compression

Time Complexity: O(E + Q * α(V)), where E is the number of equations, Q is the number of queries, V is the number of variables, and α is the inverse Ackermann function, which grows very slowly.
Space Complexity: O(V) for storing parent information and weights.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph + DFSO(Q * (V + E))O(V + E)General solution; easy to implement and ideal when query count is small
Graph + BFSO(Q * (V + E))O(V + E)Preferred when iterative traversal is easier than recursion
Union-Find with WeightsO((E + Q) α(N))O(N)Best when many queries must be answered after building relationships

Video Solution

Evaluate Division - Leetcode 399 - Python • NeetCodeIO • 62,816 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Evaluate Division easy or hard?
Evaluate Division is generally rated Medium on LeetCode. The challenge comes from modeling equations as graph relationships or implementing a weighted Union-Find structure while correctly maintaining ratio values.
How to solve Evaluate Division in O(n)?
Use a weighted Union-Find structure. Building the structure from equations takes near linear time O(E alpha(N)). Each query can then be answered in almost constant time by checking if both variables share the same root and computing the ratio from stored weights.
What is the best approach for Evaluate Division?
Two common solutions are graph traversal and weighted Union-Find. The graph approach builds an adjacency list and uses DFS or BFS to multiply ratios along a path. The Union-Find approach stores relative weights between connected variables and answers queries in near constant time using path compression.
What data structure is used in Evaluate Division?
The problem is typically solved using an adjacency list graph for DFS or BFS traversal. Another common structure is weighted Union-Find (Disjoint Set Union) where each node stores a multiplicative weight relative to its parent.
What is the time complexity of Evaluate Division?
Graph traversal solutions run in O(Q * (V + E)) where V is the number of variables, E is the number of equations, and Q is the number of queries. Weighted Union-Find improves this to roughly O((E + Q) alpha(N)), where alpha is the inverse Ackermann function and effectively constant in practice.
Evaluate Division Python or Java solution approach?
In Python, candidates often implement the graph + DFS approach using a dictionary adjacency list and recursive traversal. In Java or C++, many implementations prefer weighted Union-Find because it handles repeated queries efficiently with path compression.
Is Evaluate Division asked at Google, Amazon, or Meta?
Evaluate Division is a well-known graph and Union-Find interview problem and has appeared in coding interviews at companies like Google, Amazon, and Meta. It tests graph modeling, ratio propagation, and familiarity with disjoint set data structures.

Ready to solve this problem?

Practice Evaluate Division with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check for Contradictions in Equations

Next

Maximize Amount After Two Days of Conversions