Evaluate Division

This approach treats the problem as an all-pairs shortest path problem on a graph, but with multiplication as the path combination operator instead of addition. The Floyd-Warshall algorithm is a dynamic programming technique that computes the values of all possible divisions between variables in a single preprocessing step. After this step, any query can be answered in constant time.

1. Variable to Index Mapping: Create a mapping from each unique variable string to an integer index (from 0 to V-1, where V is the number of unique variables).
2. Matrix Initialization: Create a V x V matrix, let's call it dist. Initialize dist[i][j] to a sentinel value (e.g., -1.0) to represent that the value of var_i / var_j is unknown. Initialize the diagonal dist[i][i] to 1.0, as var_i / var_i = 1.
3. Populate Direct Edges: Iterate through the input equations. For each equation A / B = value, let i = index(A) and j = index(B). Set dist[i][j] = value and dist[j][i] = 1.0 / value.
4. Floyd-Warshall Execution: Apply the Floyd-Warshall algorithm to fill in the rest of the matrix. The standard algorithm for shortest paths is dist[i][j] = dist[i][k] + dist[k][j]. We adapt this for division: dist[i][j] = dist[i][k] * dist[k][j]. This is done using three nested loops:

   for k from 0 to V-1:
     for i from 0 to V-1:
       for j from 0 to V-1:
         if dist[i][k] != -1.0 and dist[k][j] != -1.0:
           dist[i][j] = dist[i][k] * dist[k][j]
   

5. Process Queries: For each query C / D, find their indices i = index(C) and j = index(D). The answer is dist[i][j]. If either C or D was not in the original equations, or if dist[i][j] is still the sentinel value, the answer is -1.0.

First, we map every unique variable to an integer index to facilitate the use of a 2D array (adjacency matrix). This matrix, dist, will store the results of divisions. We initialize dist[i][i] to 1.0 and populate it with the direct division values from the input equations. For A / B = V, we set dist[idx(A)][idx(B)] = V and dist[idx(B)][idx(A)] = 1/V.

The core of the approach is the Floyd-Warshall algorithm. It systematically considers every variable k as an intermediate in the path between any two other variables i and j. If we know i / k and k / j, we can compute i / j as (i / k) * (k / j). By iterating through all possible i, j, and k, we can fill the entire dist matrix with all derivable division results.

Once the matrix is fully computed, answering a query C / D is a simple lookup in the matrix. If the entry dist[idx(C)][idx(D)] was computed, that's the answer; otherwise, no relationship can be established, and we return -1.0.

import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Integer> varToIndex = new HashMap<>();
        int varCount = 0;
        for (List<String> eq : equations) {
            if (!varToIndex.containsKey(eq.get(0))) {
                varToIndex.put(eq.get(0), varCount++);
            }
            if (!varToIndex.containsKey(eq.get(1))) {
                varToIndex.put(eq.get(1), varCount++);
            }
        }

        double[][] dist = new double[varCount][varCount];
        for (int i = 0; i < varCount; i++) {
            Arrays.fill(dist[i], -1.0);
            dist[i][i] = 1.0;
        }

        for (int i = 0; i < equations.size(); i++) {
            int u = varToIndex.get(equations.get(i).get(0));
            int v = varToIndex.get(equations.get(i).get(1));
            dist[u][v] = values[i];
            dist[v][u] = 1.0 / values[i];
        }

        for (int k = 0; k < varCount; k++) {
            for (int i = 0; i < varCount; i++) {
                for (int j = 0; j < varCount; j++) {
                    if (dist[i][k] != -1.0 && dist[k][j] != -1.0) {
                        dist[i][j] = dist[i][k] * dist[k][j];
                    }
                }
            }
        }

        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            Integer start = varToIndex.get(query.get(0));
            Integer end = varToIndex.get(query.get(1));

            if (start == null || end == null) {
                results[i] = -1.0;
            } else {
                results[i] = dist[start][end];
            }
        }

        return results;
    }
}