Scale Engineer

Evaluate Division

Med
#0386Time: O(V^3 + M), where V is the number of unique variables and M is the number of queries. Since V can be at most 2N, the complexity is O(N^3 + M). The V^3 term for the Floyd-Warshall algorithm dominates.Space: O(V^2) or O(N^2), where V is the number of unique variables and N is the number of equations. This is for storing the V x V distance matrix.13 companies
Algorithms
Depth-First SearchBreadth-First SearchUnion FindShortest Path
Data structures
ArrayStringGraph
Companies
SnowflakeMakeMyTripZetaCitadel

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

  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.

Walkthrough

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;    }}

Complexity

Time

O(V^3 + M), where V is the number of unique variables and M is the number of queries. Since V can be at most 2N, the complexity is O(N^3 + M). The V^3 term for the Floyd-Warshall algorithm dominates.

Space

O(V^2) or O(N^2), where V is the number of unique variables and N is the number of equations. This is for storing the V x V distance matrix.

Trade-offs

Pros

  • Once the preprocessing is done, queries are answered in O(1) time.

  • The logic is a standard, well-known algorithm, making it relatively straightforward to implement if familiar with it.

Cons

  • The preprocessing step has a high time complexity of O(N^3), which is inefficient for larger numbers of variables.

  • It requires O(N^2) space for the adjacency matrix, which can be substantial.

Solutions

class Solution {private  Map<String, String> p;private  Map<String, Double> w;public  double[] calcEquation(List<List<String>> equations, double[] values,                        List<List<String>> queries) {    int n = equations.size();    p = new HashMap<>();    w = new HashMap<>();    for (List<String> e : equations) {      p.put(e.get(0), e.get(0));      p.put(e.get(1), e.get(1));      w.put(e.get(0), 1.0);      w.put(e.get(1), 1.0);    }    for (int i = 0; i < n; ++i) {      List<String> e = equations.get(i);      String a = e.get(0), b = e.get(1);      String pa = find(a), pb = find(b);      if (Objects.equals(pa, pb)) {        continue;      }      p.put(pa, pb);      w.put(pa, w.get(b) * values[i] / w.get(a));    }    int m = queries.size();    double[] ans = new double[m];    for (int i = 0; i < m; ++i) {      String c = queries.get(i).get(0), d = queries.get(i).get(1);      ans[i] = !p.containsKey(c) || !p.containsKey(d) ||                       !Objects.equals(find(c), find(d))                   ? -1.0                   : w.get(c) / w.get(d);    }    return ans;  }private  String find(String x) {    if (!Objects.equals(p.get(x), x)) {      String origin = p.get(x);      p.put(x, find(p.get(x)));      w.put(x, w.get(x) * w.get(origin));    }    return p.get(x);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem