Problem Statement:-
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A<sub>i</sub>, B<sub>i</sub>] and values[i] represent the equation A<sub>i</sub> / B<sub>i</sub> = values[i]. Each A<sub>i</sub> or B<sub>i</sub> is a string that represents a single variable.
You are also given some queries, where queries[j] = [C<sub>j</sub>, D<sub>j</sub>] represents the j<sup>th</sup> query where you must find the answer for C<sub>j</sub> / D<sub>j</sub> = ?.
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.
Link: https://leetcode.com/problems/evaluate-division/description/
Problem Explanation with 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 ]
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]
Explanation: [a/c can be calculated as b/c * a/b, b/c is 2.5, a/b is 1.5, therefore a/c is 3.75.] [c/b can be calculated as 1/(b/c), b/c is 2.5 therefore c/b is 0.4.] [bc/cd can be calculated as (b/c) * (c/d), b/c is 2.5, c/d is 5 therefore bc/cd is 12.5.] [cd/bc can be calculated as (c/d) * (d/c), c/d is 5, d/c is 0.2 therefore cd/bc is 0.2.]
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]
Explanation: [a/b is 0.5.] [b/a is 2.0.] [a/c is -1.0 because c does not exist in the dictionary and therefore the result is -1.] [x/y is -1.0 because x and y don't exist in the dictionary. ]
Constraints
1 <= equations.length <= 20equations[i].length == 21 <= A<sub>i</sub>.length, B<sub>i</sub>.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= C<sub>j</sub>.length, D<sub>j</sub>.length <= 5A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub>consist of lower case English letters and digits.
Intuition:-
Graph nodes can act as variables and edges can act as values. Like a -> b with edge weight 2 means a/b = 2.
We can use a graph to represent the equations and values.
Simply apply bfs on the adjacency list to find the answer else return -1.
Solution:-
Create an adjacency list which is a default dictionary to a list.
For each equation, add the edge to the adjacency list and the inverse edge. Inverse edge is the edge with the inverse value.(a/b = 2, b/a = 1/2)
Define a bfs function that takes in the source and target.
If the source or target is not in the adjacency list, then return -1. This is because we can't find the answer.
Create a queue and a visited set. Add the source to the queue and the visited set.
While the queue is not empty, pop the node and weight from the queue.
If the node is the target, then return the weight.
For each neighbor of the node, if the neighbor is not in the visited set, then add the neighbor and the weight * the weight of the edge to the queue and the visited set. This is because we want to multiply the weight of the edge to the weight of the node. (a/b = 2, b/c = 3, a/c = 6)
After the function, iterate through each query and call the bfs function on the query and append the result to the answer list.
Return the answer list.
Code:-
JAVA Solution
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, List<Pair>> adj = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
List<String> eq = equations.get(i);
String a = eq.get(0);
String b = eq.get(1);
double value = values[i];
adj.putIfAbsent(a, new ArrayList<>());
adj.putIfAbsent(b, new ArrayList<>());
adj.get(a).add(new Pair(b, value));
adj.get(b).add(new Pair(a, 1 / value));
}
double[] results = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
List<String> query = queries.get(i);
String src = query.get(0);
String target = query.get(1);
results[i] = bfs(src, target, adj);
}
return results;
}
private double bfs(String src, String target, Map<String, List<Pair>> adj) {
if (!adj.containsKey(src) || !adj.containsKey(target)) {
return -1.0;
}
Queue<Pair> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new Pair(src, 1.0));
visited.add(src);
while (!queue.isEmpty()) {
Pair curr = queue.poll();
String node = curr.node;
double weight = curr.weight;
if (node.equals(target)) {
return weight;
}
for (Pair neighbor : adj.get(node)) {
String nei = neighbor.node;
double neiWeight = neighbor.weight;
if (!visited.contains(nei)) {
queue.offer(new Pair(nei, weight * neiWeight));
visited.add(nei);
}
}
}
return -1.0;
}
private static class Pair {
String node;
double weight;
Pair(String node, double weight) {
this.node = node;
this.weight = weight;
}
}
}
Python Solution
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
adj = defaultdict(list)
for i, eq in enumerate(equations):
a,b = eq
adj[a].append([b, values[i]])
adj[b].append([a, 1/values[i]])
def bfs(src, target):
if src not in adj or target not in adj:
return -1
q = deque()
visit = set()
q.append([src, 1])
visit.add(src)
while q:
node, wt = q.popleft()
if node == target:
return wt
for nei, weight in adj[node]:
if nei not in visit:
q.append([nei, wt * weight])
visit.add(nei)
return -1
return [bfs(q[0], q[1]) for q in queries]
Complexity Analysis:-
TIME:-
The time complexity is O(n * (V + E)) where n is the number of queries, V is the number of vertices, and E is the number of edges. We visit each node once and each edge once in the worst case for each query.
SPACE:-
The space complexity is O(V + E) where V is the number of vertices and E is the number of edges. We use a default dict of length V and the call stack can go as deep as V. We also use a queue of length V and a visited set of length V.