LeetCode Solutions Blog

Evaluate Division

Number: 399

Difficulty: Medium

Paid? No

Problem Description

Given a set of equations in the form A / B = k, and a set of queries in the form C / D, determine the result of each query based on the given equations. If the answer cannot be determined, return -1.0 for that query.

Key Insights

The problem can be modeled as a graph where each variable is a node.
Each equation A / B = k creates a directed edge from A to B with weight k and from B to A with weight 1/k.
To answer a query, perform a DFS or BFS from the source node and try to reach the target node, multiplying the weights along the path.
If a variable in the query does not exist in the graph or no path exists, return -1.0.

Space and Time Complexity

Time Complexity: O(V + E) per query in the worst case since we might traverse the entire graph. Space Complexity: O(V + E) for storing the graph and the recursion stack or queue for the search.

Solution

We can solve this problem by first constructing a graph using a hashmap or dictionary where each node points to its neighbors with the corresponding multiplication factors. For each query, we perform a depth-first search (DFS) starting from the dividend. We keep track of the cumulative product along the path. If we eventually reach the divisor, we return the computed product. If not, the query is unsolvable and we return -1.0. Important points:

Use a visited set during DFS to prevent cycles.
Ensure to handle cases where either node in the query is not present in the graph.
The same approach works with BFS, but DFS may be simpler to implement in these cases.

Code Solutions

# Python solution using DFS

def calcEquation(equations, values, queries):
    # Build the graph as a dictionary of dictionaries
    graph = {}
    for (dividend, divisor), value in zip(equations, values):
        if dividend not in graph:
            graph[dividend] = {}
        if divisor not in graph:
            graph[divisor] = {}
        graph[dividend][divisor] = value
        graph[divisor][dividend] = 1 / value

    def dfs(current, target, accumulated, visited):
        # If the current node equals the target, return the accumulated product
        if current == target:
            return accumulated
        visited.add(current)
        # Traverse all neighbors
        for neighbor, value in graph[current].items():
            if neighbor in visited:
                continue
            result = dfs(neighbor, target, accumulated * value, visited)
            if result != -1:
                return result
        return -1

    results = []
    for start, end in queries:
        if start not in graph or end not in graph:
            results.append(-1.0)
        elif start == end:
            results.append(1.0)
        else:
            visited = set()
            result = dfs(start, end, 1, visited)
            results.append(result)
    return results

# Example usage:
if __name__ == "__main__":
    equations = [["a", "b"], ["b", "c"]]
    values = [2.0, 3.0]
    queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
    print(calcEquation(equations, values, queries))