399. Evaluate Division

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/evaluate-division
• topics: Graph, BFS

Description

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

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

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.

Idea

The problem involves finding a path between two nodes in a graph, where nodes are variables and edges represent the division relationship between them. The solution leverages graph traversal to compute the result for each query.

Code

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(set)  
        weights = {} 
        
        # Build graph with adjacency list and weights
        for (dividend, divisor), value in zip(equations, values):
            graph[dividend].add(divisor)
            graph[divisor].add(dividend)
            weights[(dividend, divisor)] = value
            weights[(divisor, dividend)] = 1 / value
 
        def evaluate_query(query):
            start, end = query
 
            if start not in graph or end not in graph:
                return -1.0
            
            if start == end:
                return 1.0
            
            # Perform BFS to find the result
            visited = set([start])
            queue = deque([(start, 1.0)])  # (current node, cumulative product)
            
            while queue:
                current_node, current_product = queue.popleft()
                
                for neighbor in graph[current_node]:
                    if neighbor in visited:
                        continue
                    
                    # Compute the product for the path
                    path_product = current_product * weights[(current_node, neighbor)]
                    
                    if neighbor == end:
                        return path_product  # Found the target
                    
                    visited.add(neighbor)
                    queue.append((neighbor, path_product))
            
            return -1.0  # No valid path found
 
        
        return [evaluate_query(query) for query in queries]