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.

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:

  1. Initialize Union-Find data structures.
  2. Union the nodes based on the given equations, effectively connecting the variables with edges weighted by the given values.
  3. 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.

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:

  1. We initialize two dictionaries w and p. w holds the relative weight of a variable to its root, and p holds the parent (or root representative) of each variable.
  2. We iterate over the list of equations to set up the initial connections. Each variable is initially set as a root of itself.
  3. As we go through the values alongside equations, we find the root representatives of a and b (pa and pb respectively). If they are already connected (i.e., have the same root), we skip to the next equation.
  4. If they are not connected, we connect them by setting the parent of pa to be pb and adjusting the weight of pa to maintain the correct ratio as given by the current equation. The weight of pa is updated to be the weight of b times the given value divided by the weight of a. 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:

  1. For each queries pair (c, d), we check if c or d are not present in the p dictionary. If either is not present, it means we cannot determine the ratio and hence return -1.
  2. If c and d are present, we perform find operations on both to get their root representatives.
  3. If they have different roots, the variables are in different disjoint sets, and we cannot determine their ratio, so we return -1.
  4. If c and d belong to the same connected component (have the same root), we return the ratio by dividing w[c] by w[d]. This works because w[c] represents the ratio of c to its root and w[d] of d to that same root, so their division gives the ratio c/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.

💪
Level Up Your
Algo Skills

Example 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:

  1. We intialize two dictionaries w and p to keep track of weights and parents.

  2. We start processing the equations:

    For the first equation ["a", "b"]:

    • We find the root of a (which is a itself since it's the first time we see it) and do the same for b.
    • We union a and b, by making b the parent of a's root and we set the weight of a to 2.0 (since a / 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 is b itself).
    • Find the root of c (which is c itself).
    • We union b and c, making c the parent of b's root and updating the weight of b to 3.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"}
  3. Now we handle the queries one by one:

    • For ["a", "c"]:

      • Find root of a (which is c through b), and find root of c (which is c).
      • Since the roots are the same, we can find the ratio by dividing w[a] by w[c], so a / c = w[a] / w[c] = 2.0 / 1.0 = 2.0.
    • For ["c", "b"]:

      • Roots for both c and b are c, so they are connected.
      • We get the ratio c / b = w[c] / w[b] = 1.0 / 3.0 = 0.333....
    • For ["b", "a"]:

      • Roots for both b and a are c, so they are connected.
      • We get the ratio b / a = w[b] / w[a] = 3.0 / 2.0 = 1.5.
    • For ["a", "e"]:

      • e is not found in p, so there is no known connection between a and e.
      • 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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    }
56    return parent[x];
57}
58

Time and Space Complexity

Time Complexity

The given Python code implements a solution to evaluate division among a set of variables based on given equations. Here's the breakdown of its time complexity:

  • The initialization of variables w and p: The complexity for this is constant, O(1).

  • The first for-loop iterates through the list of equations. If there are E equations, this loop runs E times, contributing an O(E) complexity.

  • The second for-loop iterates through the list of values, with parallel iteration over the equations again, thus running E times. Within this loop, the find function is called for each a and b, which can lead to a depth of E in the worst-case if every find leads to another find. However, due to path compression, the amortized time complexity for each find operation drops to near O(1), so the loop contributes O(E) complexity.

  • The last for-loop iterates over the list of queries. Let's say there are Q queries; this loop runs Q times. Inside this loop, there is also a find call for each c and d, which again is amortized to O(1) complexity due to path compression. This loop, therefore, adds an O(Q) complexity.

Combining all the parts, the resultant time complexity is: O(E + E + Q) which simplifies to O(E + Q), given E is the number of equations, and Q is the number of queries.

Space Complexity

Here's the breakdown of space complexity for the given code:

  • The w (weights) and p (parents) dictionaries will at most store every unique variable from both equations and queries. If V represents the total distinct variables, then these structures will contribute O(V) to the space complexity.

  • The output list is composed of an entry for each query. If there are Q queries, this will contribute O(Q) space complexity.

Therefore, the total space complexity is O(V + Q), where V is the number of distinct variables, and Q is the number of queries.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫