399.Evaluate_Division(Medium).md

399. Evaluate Division (Medium)

Date and Time: Aug 10, 2024, 18:18 (EST)

Link: https://leetcode.com/problems/evaluate-division/

Question:

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries [j] = [C_j, D_j] represents the jth query where you must find the answer for C_j / D_j = ?.

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

• A_i, B_i, C_j, D_j consist of lower case English letters and digits.

Walk-through:

1. We can build a graph to store all variable pairs into a dictionary adj{} with their value, so for equations = [["a", "b"]], values = [2.0], we store adj = {"a": ['b', 2.0], 'b': ['a', 0.5]}. From a -> b, we store 2.0, from b -> a, we store 1 / 2 = 0.5.

2. Then we run BFS on all variable pairs from queries in a list-comprehension.

3. If src or target from queries is not in adj{}, we return -1. Then, we use deque[] to pop-left each variable pair (var, w) we stored to find when var == target and we just return w, if not found, we append all adj[var]'s neighbors with their weight * w we popped-left from deque[].

Python Solution:

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        adj = collections.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
            deque, visited = collections.deque(), set()
            deque.append([src, 1])
            visited.add(src)
            while deque:
                var, w = deque.popleft()
                if var == target:
                    return w
                for neighbor, weight in adj[var]:
                    if neighbor not in visited:
                        deque.append([neighbor, w * weight])
                        visited.add(neighbor)
            return -1

        return [bfs(q[0], q[1]) for q in queries]

Time Complexity: $O(n * (V + E))$, n is for number of pairs times the complexity to traverse the whole graph in BFS/DFS in O(V + E).
Space Complexity: $O(V + E)$ to store the whole graph.