We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Evaluate Division

Difficulty: Medium

Problem Description

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 j-th 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. 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.

Key Insights

  • The problem can be represented as a graph where each variable is a node and the division relationships represent directed edges with weights.
  • A depth-first search (DFS) or breadth-first search (BFS) can be used to find the path between queried variables.
  • If a variable is not found in the graph, the result for that query should be -1.0.
  • The union-find algorithm can also be utilized to efficiently manage and query connected components of the graph.

Space and Time Complexity

Time Complexity: O(V + E + Q), where V is the number of unique variables, E is the number of equations, and Q is the number of queries.
Space Complexity: O(V), to store the graph representation.

Solution

To solve the problem, we can represent the equations as a graph using an adjacency list where each variable points to its neighbors along with the corresponding division values. We can then perform a DFS or BFS to evaluate each query by finding a path from the numerator to the denominator. If the path exists, we multiply the values along the path to obtain the result; otherwise, we return -1.0.

Code Solutions

from collections import defaultdict

def calcEquation(equations, values, queries):
    graph = defaultdict(dict)

    # Build the graph
    for (a, b), value in zip(equations, values):
        graph[a][b] = value
        graph[b][a] = 1 / value

    def dfs(start, end, visited):
        if start not in graph or end not in graph:
            return -1.0
        if start == end:
            return 1.0
        visited.add(start)
        for neighbor, value in graph[start].items():
            if neighbor not in visited:
                result = dfs(neighbor, end, visited)
                if result != -1.0:
                    return result * value
        visited.remove(start)
        return -1.0

    results = []
    for a, b in queries:
        results.append(dfs(a, b, set()))
    
    return results
← Back to All Questions