399. Evaluate Division
Problem Description
The problem presented involves understanding and calculating the ratios between various variables given some base equations and then using this information to solve a series of queries for the ratios between other pairs of variables. Specifically, we are given an array of equations
where each element is a pair [A_i, B_i]
that represents a single equation A_i / B_i
. Alongside, there is an array of values
where values[i]
represents the value of the ith equation, A_i / B_i = values[i]
.
Our task is to answer a series of queries
where each query [C_j, D_j]
asks for the value of C_j / D_j
. If we can determine the answer based on the given equations and values, we should include it in our output. If we cannot determine the answer (for example, if one or both of the variables don't appear in the given equations, or if there is no connection between them through the equations), we should return -1.0 for that query.
It is guaranteed that the input will be valid, meaning that no division by zero will occur, all equations are possible, and there are no contradictory equations.
Flowchart Walkthrough
To analyze Leetcode 399: Evaluate Division, let's employ the algorithm flowchart for guidance. The problem involves equations given as fractions, which are essentially ratios between values, and you need to compute results for queries based on these equations. It can be thought of as a graph problem where each variable represents a node and each equation represents an edge with a certain weight.
Follow along the Flowchart per the steps:
Is it a graph?
- Yes: Each variable can be represented as a node. Each division equation represents a directed edge between nodes. The weight of the edge is the result of the division.
Is it a tree?
- No: The graph is not necessarily a hierarchy without cycles. In fact, cycles are allowed because you can go from one variable to another and back using different division results.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The graph could have cycles because you can derive multiple paths that reflect different derived equations.
Is the problem related to shortest paths?
- No: The problem isn't about finding shortest paths; it's about finding specific relationships (or weights) between connected nodes.
Does the problem involve connectivity?
- Yes: The problem involves checking if two variables are connected and finding the product of the weights (division results or ratios) along the path between these variables.
Is the graph weighted?
- Yes: Each edge in the graph has a weight, which is the division result between the two connected nodes.
Since this weighted connectivity problem doesn't have anything to do with minimum paths or similar shortest-path conditions, and the graph may include cycles, the Depth-First Search (DFS) algorithm is suitable. DFS can be efficiently used to explore all possible connections between nodes, recursively multiplying the weights of the edges to compute the result for each query.
Conclusion: Based on the journey through the flowchart where the path involves determining connectivity in a weighted graph with cycles, DFS is the appropriate algorithm for efficiently solving the Evaluate Division problem.
Intuition
The intuition behind solving this problem lies in recognizing it as a graph problem. Each variable can be thought of as a node in a graph, and each equation as an edge that connects two variables. The value associated with each equation is the weight of the corresponding edge.
Using this interpretation, the problem of finding the ratio of two variables becomes a problem of finding a path between two nodes in the graph. If there's a direct path between the nodes (variables) representing the numerator and denominator, we can calculate the result; if not, or if one of the variables doesn't exist in the graph, the result is -1.0.
To efficiently find the connections and calculate the ratios between variables, we can use the Union-Find algorithm, which is suitable for handling such dynamic connectivity problems. It helps track which variables are connected and combines groups of connected components efficiently.
Here's how we arrive at the solution approach:
- Initialize Union-Find data structures.
- Union the nodes based on the given equations, effectively connecting the variables with edges weighted by the given values.
- Iterate over the queries, for each:
- If both variables are in the graph and belong to the same connected component, calculate the ratio using the weights along the path that connects the variables.
- If the variables are not in the same connected component or at least one is not in the graph, return -1.0 for that query.
The solution uses path compression in the Union-Find find
function, which optimizes the structure by making nodes in the path point directly to the root. As we call find
, we simultaneously update the weights (w
) to ensure direct access to the relative weight of any node to its root. This optimization allows for faster queries following the construction of the graph.
In summary, the solution approach employs a graph representation and Union-Find algorithm with path compression to efficiently solve the ratio queries.
Learn more about Depth-First Search, Breadth-First Search, Union Find, Graph and Shortest Path patterns.
Solution Approach
The reference solution approach mentions "Union find," which is a data structure that is particularly adept at handling the "disjoint-set" class of problems. In this problem, we are working with variables that are members of certain groups—where each group represents the variables that have been equated through the given equations.
The Union-Find
data structure has two primary operations:
find
: This function determines the root representative of a set that an element belongs to, and it also applies path compression here.union
: This function merges two sets together.
In the provided Python code, we have a find
function that handles finding the root representative and path compression, but instead of a separate union
function, the union operation is embedded within the main logic of the calcEquation
method:
- We initialize two dictionaries
w
andp
.w
holds the relative weight of a variable to its root, andp
holds the parent (or root representative) of each variable. - We iterate over the list of
equations
to set up the initial connections. Each variable is initially set as a root of itself. - As we go through the
values
alongsideequations
, we find the root representatives ofa
andb
(pa
andpb
respectively). If they are already connected (i.e., have the same root), we skip to the next equation. - If they are not connected, we connect them by setting the parent of
pa
to bepb
and adjusting the weight ofpa
to maintain the correct ratio as given by the current equation. The weight ofpa
is updated to be the weight ofb
times the given value divided by the weight ofa
. This ensures that the weight reflects the ratio between these two connected components up to their common root.
Once the equations
are processed and the Union-Find structure is ready, we handle the queries
:
- For each
queries
pair(c, d)
, we check ifc
ord
are not present in thep
dictionary. If either is not present, it means we cannot determine the ratio and hence return-1
. - If
c
andd
are present, we performfind
operations on both to get their root representatives. - If they have different roots, the variables are in different disjoint sets, and we cannot determine their ratio, so we return
-1
. - If
c
andd
belong to the same connected component (have the same root), we return the ratio by dividingw[c]
byw[d]
. This works becausew[c]
represents the ratio ofc
to its root andw[d]
ofd
to that same root, so their division gives the ratioc/d
.
This code thus uses Union-Find with path compression to implement a fast and efficient solution to the problem, handling both the input equations to build the graph as well as the queries to extract the required ratios.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example.
Suppose we have the following input:
equations
:[["a", "b"], ["b", "c"]]
values
:[2.0, 3.0]
queries
:[["a", "c"], ["c", "b"], ["b", "a"], ["a", "e"]]
Here equations
and values
tell us that a / b = 2.0
and b / c = 3.0
.
Using the solution approach:
-
We intialize two dictionaries
w
andp
to keep track of weights and parents. -
We start processing the
equations
:For the first equation
["a", "b"]
:- We find the root of
a
(which isa
itself since it's the first time we see it) and do the same forb
. - We union
a
andb
, by makingb
the parent ofa
's root and we set the weight ofa
to2.0
(sincea / b = 2.0
).
The dictionaries are now:
w = {"a": 2.0, "b": 1.0}
p = {"a": "b", "b": "b"}
For the second equation
["b", "c"]
:- Find the root of
b
(which isb
itself). - Find the root of
c
(which isc
itself). - We union
b
andc
, makingc
the parent ofb
's root and updating the weight ofb
to3.0
(b / c = 3.0
).
The dictionaries are now updated:
w = {"a": 2.0, "b": 3.0, "c": 1.0}
p = {"a": "b", "b": "c", "c": "c"}
- We find the root of
-
Now we handle the queries one by one:
-
For
["a", "c"]
:- Find root of
a
(which isc
throughb
), and find root ofc
(which isc
). - Since the roots are the same, we can find the ratio by dividing
w[a]
byw[c]
, soa / c = w[a] / w[c] = 2.0 / 1.0 = 2.0
.
- Find root of
-
For
["c", "b"]
:- Roots for both
c
andb
arec
, so they are connected. - We get the ratio
c / b = w[c] / w[b] = 1.0 / 3.0 = 0.333...
.
- Roots for both
-
For
["b", "a"]
:- Roots for both
b
anda
arec
, so they are connected. - We get the ratio
b / a = w[b] / w[a] = 3.0 / 2.0 = 1.5
.
- Roots for both
-
For
["a", "e"]
:e
is not found inp
, so there is no known connection betweena
ande
.- We return
-1.0
for this query.
-
At the end of the process, the results for the queries are [2.0, 0.333..., 1.5, -1.0]
. Through the Union-Find algorithm with path compression, we were able to efficiently solve for the ratios between various variables.
Solution Implementation
1from collections import defaultdict
2from typing import List
3
4class Solution:
5 def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
6
7 # This function finds the root of the set to which 'x' belongs
8 # It uses path compression to make subsequent lookups faster
9 def find(x):
10 if parent[x] != x:
11 original_parent = parent[x]
12 parent[x] = find(parent[x]) # Recursively find the root parent
13 weight[x] *= weight[original_parent] # Adjust the weight
14 return parent[x]
15
16 # Initialize default dictionary for weights and parents
17 weight = defaultdict(lambda: 1.0)
18 parent = defaultdict(str)
19
20 # Set initial parent of each variable to itself
21 for a, b in equations:
22 parent[a], parent[b] = a, b
23
24 # Process each equation and union the groups setting the parent relationship and weight
25 for i, value in enumerate(values):
26 a, b = equations[i]
27 root_a, root_b = find(a), find(b)
28
29 if root_a != root_b: # If 'a' and 'b' have different roots, union them
30 parent[root_a] = root_b
31 weight[root_a] = weight[b] * value / weight[a]
32
33 # Process each query
34 results = []
35 for c, d in queries:
36 # If either variable is unknown, or they belong to different sets, the result is -1
37 if c not in parent or d not in parent or find(c) != find(d):
38 results.append(-1.0)
39 else:
40 # If they belong to the same set, calculate the result based on weights
41 results.append(weight[c] / weight[d])
42
43 return results
44
45# Usage example:
46# sol = Solution()
47# equations = [["a", "b"], ["b", "c"]]
48# values = [2.0, 3.0]
49# queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
50# results = sol.calcEquation(equations, values, queries)
51# print(results)
52
1class Solution {
2 private Map<String, String> parent;
3 private Map<String, Double> weight;
4
5 public double[] calcEquation(
6 List<List<String>> equations, double[] values, List<List<String>> queries) {
7
8 // Initialize the parent and weight maps for union-find structure
9 parent = new HashMap<>();
10 weight = new HashMap<>();
11
12 // Create a union-find structure to represent the equations
13 for (List<String> equation : equations) {
14 parent.put(equation.get(0), equation.get(0));
15 parent.put(equation.get(1), equation.get(1));
16 weight.put(equation.get(0), 1.0);
17 weight.put(equation.get(1), 1.0);
18 }
19
20 int equationCount = equations.size();
21
22 // Perform union operations
23 for (int i = 0; i < equationCount; ++i) {
24 List<String> equation = equations.get(i);
25 String varA = equation.get(0), varB = equation.get(1);
26 String parentA = find(varA), parentB = find(varB);
27 if (!Objects.equals(parentA, parentB)) {
28 parent.put(parentA, parentB);
29 weight.put(parentA, weight.get(varB) * values[i] / weight.get(varA));
30 }
31 }
32
33 int queryCount = queries.size();
34 double[] answers = new double[queryCount];
35
36 // Evaluate each query
37 for (int i = 0; i < queryCount; ++i) {
38 String varC = queries.get(i).get(0), varD = queries.get(i).get(1);
39 if (!parent.containsKey(varC) || !parent.containsKey(varD) ||
40 !Objects.equals(find(varC), find(varD))) {
41 // If the variables do not belong to the same set, or at least one of the
42 // variables is not part of any equation, the answer is -1
43 answers[i] = -1.0;
44 } else {
45 answers[i] = weight.get(varC) / weight.get(varD);
46 }
47 }
48 return answers;
49 }
50
51 // The find function for the union-find structure
52 private String find(String x) {
53 if (!Objects.equals(parent.get(x), x)) {
54 String originalParent = parent.get(x);
55 parent.put(x, find(parent.get(x))); // Path compression
56 weight.put(x, weight.get(x) * weight.get(originalParent));
57 }
58 return parent.get(x);
59 }
60}
61
1class Solution {
2public:
3 // Parent mapping and weight mapping for union-find structure
4 unordered_map<string, string> parent;
5 unordered_map<string, double> weight;
6
7 // Function to evaluate division results for given division equations
8 vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
9 int equationCount = equations.size();
10
11 // Initialize the parents and weights for the disjoint set
12 for (const auto& equation : equations) {
13 parent[equation[0]] = equation[0];
14 parent[equation[1]] = equation[1];
15 weight[equation[0]] = 1.0;
16 weight[equation[1]] = 1.0;
17 }
18
19 // Perform Union operation
20 for (int i = 0; i < equationCount; ++i) {
21 const auto& equation = equations[i];
22 const string& varA = equation[0];
23 const string& varB = equation[1];
24 string parentA = find(varA);
25 string parentB = find(varB);
26
27 // If they already have the same parent, they are already connected
28 if (parentA == parentB) continue;
29
30 // Union the two sets and adjust the weights
31 parent[parentA] = parentB;
32 weight[parentA] = weight[varB] * values[i] / weight[varA];
33 }
34
35 int queryCount = queries.size();
36 vector<double> answers(queryCount);
37
38 // Process queries
39 for (int i = 0; i < queryCount; ++i) {
40 const string& varC = queries[i][0];
41 const string& varD = queries[i][1];
42
43 // Check whether the variables are present in the union-find structure and connected
44 if (parent.find(varC) == parent.end() || parent.find(varD) == parent.end() || find(varC) != find(varD)) {
45 answers[i] = -1.0; // Variables are disconnected or not present
46 } else {
47 answers[i] = weight[varC] / weight[varD]; // Compute the ratio
48 }
49 }
50
51 return answers;
52 }
53
54 // Helper function to perform Find operation in the union-find data structure
55 string find(string x) {
56 if (parent[x] != x) {
57 string originParent = parent[x];
58 parent[x] = find(parent[x]); // Path compression
59 weight[x] *= weight[originParent]; // Adjust weights during path compression
60 }
61 return parent[x];
62 }
63};
64
1// Global variable to hold parent mapping and weight mapping for union-find structure
2const parent: {[key: string]: string} = {};
3const weight: {[key: string]: number} = {};
4
5// Evaluate division results for given division equations
6function calcEquation(
7 equations: [string, string][],
8 values: number[],
9 queries: [string, string][]
10): number[] {
11
12 // Initialize the parents and weights for the disjoint set
13 for (const [dividend, divisor] of equations) {
14 parent[dividend] = dividend;
15 parent[divisor] = divisor;
16 weight[dividend] = 1.0;
17 weight[divisor] = 1.0;
18 }
19
20 // Perform union operation
21 for (let i = 0; i < equations.length; ++i) {
22 const [varA, varB] = equations[i];
23 const parentA = find(varA);
24 const parentB = find(varB);
25
26 // If they already have the same parent, they are already connected
27 if (parentA === parentB) continue;
28
29 // Union the two sets and adjust the weights
30 parent[parentA] = parentB;
31 weight[parentA] = weight[varB] * values[i] / weight[varA];
32 }
33
34 // Process queries
35 const answers: number[] = [];
36
37 for (let [varC, varD] of queries) {
38 // Check whether the variables are present in the union-find structure and connected
39 if (!(varC in parent) || !(varD in parent) || find(varC) !== find(varD)) {
40 answers.push(-1.0); // Variables are disconnected or not present
41 } else {
42 answers.push(weight[varC] / weight[varD]); // Compute the ratio
43 }
44 }
45
46 return answers;
47}
48
49// Helper function to perform Find operation in the union-find data structure
50function find(x: string): string {
51 if (parent[x] !== x) {
52 const originalParent = parent[x];
53 parent[x] = find(parent[x]); // Path compression
54 weight[x] *= weight[originalParent]; // Adjust weights during path compression
55 }