Sponsored
Sponsored
Approach: Represent the given variable equations as a graph. Each variable is a node, and an equation between two variables becomes a directed edge with a weight from one node to another representing the ratio. To find the result of a query, search for a path from the dividend node to the divisor node using Depth First Search (DFS). If a path is found, multiply the weights along the path to get the result. If no path is found, return -1.0 as the result cannot be determined.
Time Complexity: O(V + E) for each query, where V is the number of variables and E is the number of equations due to the DFS traversal. Overall complexity is O(Q * (V + E)) for Q queries.
Space Complexity: O(V + E) for storing the graph.
1function calcEquation(equations, values, queries) {
2 const graph = new Map();
3
4 // Build the graph
5 equations.forEach(([start, end], i) => {
6 if (!graph.has(start)) graph.set(start, new Map());
7 if (!graph.has(end)) graph.set(end, new Map());
8 graph.get(start).set(end, values[i]);
9 graph.get(end).set(start, 1 / values[i]);
10 });
11
12 function dfs(start, end, visited, product) {
13 if (!graph.has(start)) return -1.0;
14
15 if (start === end) return product;
16
17 visited.add(start);
18
19 const neighbors = graph.get(start);
20 for (const [next, value] of neighbors) {
21 if (!visited.has(next)) {
22 const result = dfs(next, end, visited, product * value);
23 if (result !== -1.0) return result;
24 }
25 }
26
27 visited.delete(start);
28 return -1.0;
29 }
30
31 return queries.map(([dividend, divisor]) => {
32 return dfs(dividend, divisor, new Set(), 1.0);
33 });
34}The JavaScript implementation also constructs a graph using a Map of Maps for easy traversal. It applies DFS to recursively find the connection between two variables in a query. If there's a path from the dividend to the divisor, it computes the result by multiplying the edge weights along that path. The code handles non-existent nodes by returning -1.0 for such cases.
Approach: Use Union-Find (Disjoint Set Union, DSU) with path compression to represent connected components of variables where each component can efficiently find the "parent" or representative of a set. Each variable is associated with a weight that represents its relative scale with respect to its parent. This method efficiently handles union operations and queries to determine the result by finding the root of each variable and combining their scales.
Time Complexity: O(E + Q * α(V)), where E is the number of equations, Q is the number of queries, V is the number of variables, and α is the inverse Ackermann function, which grows very slowly.
Space Complexity: O(V) for storing parent information and weights.
1#include <unordered_map>
2#include <vector>
3#include <string>
4
using namespace std;
class Solution {
public:
vector<double> calcEquation(
vector<vector<string>>& equations,
vector<double>& values,
vector<vector<string>>& queries) {
unordered_map<string, pair<string, double>> parents;
// Find function with path compression
function<pair<string, double>(string)> find = [&](string v) {
if (!parents.count(v)) return make_pair(v, 1.0);
auto& [p, w] = parents[v];
if (v != p) {
auto result = find(p);
parents[v] = {result.first, w * result.second};
}
return parents[v];
};
// Union function
auto unite = [&](string v1, string v2, double ratio) {
auto [root1, weight1] = find(v1);
auto [root2, weight2] = find(v2);
if (root1 != root2) {
parents[root2] = {root1, ratio * weight1 / weight2};
}
};
for (int i = 0; i < equations.size(); ++i) {
const auto& eq = equations[i];
unite(eq[0], eq[1], values[i]);
}
vector<double> results;
for (const auto& query : queries) {
if (!parents.count(query[0]) || !parents.count(query[1])) {
results.push_back(-1.0);
continue;
}
auto [root1, weight1] = find(query[0]);
auto [root2, weight2] = find(query[1]);
if (root1 != root2) {
results.push_back(-1.0);
} else {
results.push_back(weight1 / weight2);
}
}
return results;
}
};This C++ solution uses a Union-Find data structure with path compression. For each equation, it unifies the variables into a single component, maintaining their relative ratios. For each query, it determines whether the variables are in the same component and calculates the result using the stored weights (which represent ratios to their respective roots).