Evaluate Division

Problem Statement

In this problem, you are provided with two sets of data:

1. An array of equations represented by pairs of variables, where each pair correlates to an equation depicting the division of the first variable by the second variable, alongside an array of values that specify the result of these divisions.
2. Queries that require a set of results based on the given equations.

Each equation pair and its corresponding value concretely establish the relationship between two variables in the format Ai / Bi = values[i]. Each variable (Ai or Bi) is denoted by a string. You are tasked with responding to several queries, each seeking the result of a division between two specified variables.

You need to compute the results for these queries based on the established relationships from the given equations. If a result cannot be conclusively determined based on the given data, the function should return -1.0.

The main challenge lies in determining the results utilizing the transitive relationships derived from the equations. For example, if the equations establish relationships between a and b, as well as b and c, you may also need to deduce the relationship between a and c.

It's important to remember:

• The input data is always valid, and thus won't directly cause execution errors such as zero division.
• Variables not defined in the equations have no established relationships, meaning their division result is undefined, equating to -1.0.

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

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 and Intuition

The solution to this problem involves constructing a graphical representation of the equations where each variable is a node and the division value forms the weight of the directed edge between the nodes. This method uses concepts from graph theory to solve the problem efficiently.

Steps:

1. Construct a directed graph:

   • Variables in the equations act as nodes.
   • An equation Ai / Bi = value introduces a directed edge from Ai to Bi with weight equal to value.
   • To enable inverse lookups, add an additional edge from Bi to Ai with the weight 1 / value.

2. For each query (Cj, Dj), determine if Cj can be reached from Dj using any path in the constructed graph:

   • If Cj or Dj or both do not exist in the graph, the result is -1.0 since they are undefined based on the equations.
   • If they exist, use depth-first search (DFS) or breadth-first search (BFS) to find a path from Cj to Dj and calculate the cumulative product of the weights along this path.

Graphical traversal for path finding:

• Using BFS, start from node Cj, traverse to all reachable nodes. If Dj is reached, the cumulative product of the traversal gives the required division value.
• A failure to reach Dj signifies no discernible relationship based on the given equations, returning -1.0.

This approach fully explores the potential relationships between variables as represented by the graph structure, taking into account both direct and derived relationships, ensuring a comprehensive solution to the queries based on the dataset provided.

Solutions

class Solution {
    
    public double[] calculateRatios(List<List<String>> equations, double[] values,
            List<List<String>> queries) {
    
        HashMap<String, Pair<String, Double>> groupMap = new HashMap<>();
    
        // Building the map
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String numerator = equation.get(0), denominator = equation.get(1);
            double quotient = values[i];
    
            mergeGroups(groupMap, numerator, denominator, quotient);
        }
    
        // Evaluating each query
        double[] outcomes = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String numerator = query.get(0), denominator = query.get(1);
    
            if (!groupMap.containsKey(numerator) || !groupMap.containsKey(denominator))
                outcomes[i] = -1.0;
            else {
                Pair<String, Double> numeratorGroup = locate(groupMap, numerator);
                Pair<String, Double> denominatorGroup = locate(groupMap, denominator);
    
                String numeratorRoot = numeratorGroup.getKey();
                String denominatorRoot = denominatorGroup.getKey();
                Double numeratorWeight = numeratorGroup.getValue();
                Double denominatorWeight = denominatorGroup.getValue();
    
                if (!numeratorRoot.equals(denominatorRoot))
                    outcomes[i] = -1.0;
                else
                    outcomes[i] = numeratorWeight / denominatorWeight;
            }
        }
    
        return outcomes;
    }
    
    private Pair<String, Double> locate(HashMap<String, Pair<String, Double>> groupMap, String item) {
        if (!groupMap.containsKey(item))
            groupMap.put(item, new Pair<String, Double>(item, 1.0));
    
        Pair<String, Double> entry = groupMap.get(item);
        // Correcting inconsistencies dynamically
        if (!entry.getKey().equals(item)) {
            Pair<String, Double> newGroup = locate(groupMap, entry.getKey());
            groupMap.put(item, new Pair<String, Double>(
                    newGroup.getKey(), entry.getValue() * newGroup.getValue()));
        }
    
        return groupMap.get(item);
    }
    
    private void mergeGroups(HashMap<String, Pair<String, Double>> groupMap, String num, String denom, Double ratio) {
        Pair<String, Double> numEntry = locate(groupMap, num);
        Pair<String, Double> denomEntry = locate(groupMap, denom);
    
        String numRoot = numEntry.getKey();
        String denomRoot = denomEntry.getKey();
        Double numWeight = numEntry.getValue();
        Double denomWeight = denomEntry.getValue();
    
        if (!numRoot.equals(denomRoot)) {
            groupMap.put(numRoot, new Pair<String, Double>(denomRoot,
                    denomWeight * ratio / numWeight));
        }
    }
}