NUHMAN.com

📘 Problem Statement

You are given an array of equations, where each equation is of the form A / B = k, representing A divided by B equals k. You are also given an array of queries, where each query is of the form A / B, and you need to evaluate the value of each query based on the equations.

• Equations: An array of equations, where each equation is represented by [A, B, k], meaning A / B = k.
• Queries: An array of queries, where each query is represented by [A, B], and you need to find the value of A / B.

The goal is to calculate the value of each query based on the given equations.

Note:

• The equations are all valid, and each variable is a non-zero alphabetic character.
• The result of a query should be -1.0 if there is no possible way to compute the value (i.e., if the equation cannot be solved with the given set of equations).

📚 Example:

python

Input:
equations = [["a", "b", 2.0], ["b", "c", 3.0]]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]

Output:
[6.0, 0.5, -1.0, 1.0, -1.0]

Explanation:
- "a / c" = "a / b" * "b / c" = 2.0 * 3.0 = 6.0
- "b / a" = 1 / (a / b) = 1 / 2.0 = 0.5
- "a / e" = no path from a to e = -1.0
- "a / a" = 1.0
- "x / x" = no path from x to x = -1.0

🧠 Key Insight

This problem can be efficiently solved using graph theory. Each variable can be considered as a node in a graph, and each equation represents an edge with a weight. The weight of an edge is the division result (i.e., k in the equation A / B = k).

We can represent the equations as a graph:

• Each variable is a node.
• Each equation A / B = k is an edge connecting A and B with a weight of k.

To evaluate each query, we need to find the path between the two nodes involved in the query. If a path exists, we compute the product of the edge weights along that path to get the result.

💡 Approach

1. Graph Representation:

• Create a graph where each variable is a node.
• For each equation, add an edge between the two variables with the corresponding weight.

1. Graph Traversal:

• Use DFS (Depth-First Search) or Union-Find to find a path between the nodes involved in a query.
• If a path exists, compute the product of the edge weights; otherwise, return -1.0.

1. DFS Implementation:

• We will use DFS to find the path between the two nodes.
• During the DFS, if we encounter the destination node, we calculate the product of the edge weights along the path.

1. Union-Find (Alternative approach):

• We can use Union-Find (Disjoint Set Union - DSU) to group connected components and compute the result efficiently.

🐍 Python Code

python

class Solution:
    def calcEquation(self, equations: list[list[str]], queries: list[list[str]]) -> list[float]:
        # Step 1: Build the graph
        graph = {}
        for A, B, k in equations:
            if A not in graph:
                graph[A] = {}
            if B not in graph:
                graph[B] = {}
            graph[A][B] = k
            graph[B][A] = 1 / k

        # Step 2: DFS function to find the result of the division
        def dfs(curr, target, visited):
            if curr == target:
                return 1
            visited.add(curr)
            for neighbor, value in graph[curr].items():
                if neighbor not in visited:
                    result = dfs(neighbor, target, visited)
                    if result != -1:
                        return value * result
            return -1

        # Step 3: Process each query
        result = []
        for A, B in queries:
            if A not in graph or B not in graph:
                result.append(-1.0)
            else:
                visited = set()
                result.append(dfs(A, B, visited))
        
        return result

🔍 Step-by-Step Explanation

1. Graph Representation:

python

graph = {}
for A, B, k in equations:
    if A not in graph:
        graph[A] = {}
    if B not in graph:
        graph[B] = {}
    graph[A][B] = k
    graph[B][A] = 1 / k

• For each equation A / B = k, we add an edge between nodes A and B with weight k in one direction, and 1/k in the other direction (since division is bidirectional).
• This results in a graph where each node (variable) is connected to other nodes via weighted edges representing the division relationships.

2. DFS Function:

python

def dfs(curr, target, visited):
    if curr == target:
        return 1
    visited.add(curr)
    for neighbor, value in graph[curr].items():
        if neighbor not in visited:
            result = dfs(neighbor, target, visited)
            if result != -1:
                return value * result
    return -1

• The dfs function performs a depth-first search from the current node (curr) to the target node (target).
• If the target is found, the function returns the product of edge weights along the path.
• If no path exists, the function returns -1.

3. Process Each Query:

python

result = []
for A, B in queries:
    if A not in graph or B not in graph:
        result.append(-1.0)
    else:
        visited = set()
        result.append(dfs(A, B, visited))

• For each query, we check if both nodes (A and B) exist in the graph.
• If either of the nodes does not exist, the result is -1.0.
• If both nodes exist, we perform DFS to find the result of the division.

💡 Example Walkthrough

Example 1:

python

Input:
equations = [["a", "b", 2.0], ["b", "c", 3.0]]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]

Output:
[6.0, 0.5, -1.0, 1.0, -1.0]

1. Graph Construction:

• a is connected to b with weight 2.0.
• b is connected to a with weight 1/2.0.
• b is connected to c with weight 3.0.
• c is connected to b with weight 1/3.0.

1. Processing Queries:

• "a / c": We find the path a -> b -> c, and the result is 2.0 * 3.0 = 6.0.
• "b / a": We find the path b -> a, and the result is 1 / 2.0 = 0.5.
• "a / e": No path from a to e, so the result is -1.0.
• "a / a": The result is always 1.0 since any variable divided by itself is 1.
• "x / x": No path from x to x, so the result is -1.0.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(E + Q * V)Space ComplexityO(E + V)

• Time Complexity:
• E is the number of edges (equations), and V is the number of vertices (variables).
• For each query, we perform a DFS which has a time complexity of O(V). Hence, the total time complexity for Q queries is O(Q * V), plus the time to build the graph, which is O(E).
• Space Complexity:
• We store the graph with E edges and V vertices, so the space complexity is O(E + V).

🧵 Final Thoughts

LeetCode 399 is a great problem that introduces the application of graph theory and traversal algorithms to solve real-world problems like division equations. By representing the equations as a graph, we can efficiently compute the results of division queries using depth-first search (DFS).