⚡Flashcard Drill➔
NeetCode #597LC-399MediumGraphsNC 250
← Back to All Problems

#597 · #399 · Evaluate Division(除法求值)

📌 Problem Statement & Constraints

You are given equations where equations[i] = [Ai, Bi] and values[i] means Ai / Bi = values[i]. Given queries, return the answer to each query Cj / Dj, or -1.0 if it cannot be determined. Constraints: 1 <= equations.length <= 20, 1 <= queries.length <= 20, variables are strings.

💡 Core Algorithmic Approaches

  1. Model the variables as nodes in a weighted graph: an edge A -> B has weight A / B.
  2. A query C / D is the product of edge weights along a path from C to D.
  3. DFS from the source, multiplying weights as you descend, and stop when the target is found.
  4. Unknown variables or disconnected pairs yield -1.0.

💻 Benchmark Python3 Implementation

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        from collections import defaultdict
        g = defaultdict(list)
        for (a, b), v in zip(equations, values):
            g[a].append((b, v))            # a / b = v
            g[b].append((a, 1 / v))        # b / a = 1/v

        def dfs(src: str, dst: str, visited: set) -> float:
            if src not in g or dst not in g:
                return -1.0                # unknown variable
            if src == dst:
                return 1.0
            visited.add(src)
            for nxt, w in g[src]:
                if nxt in visited:
                    continue
                if nxt == dst:
                    return w
                sub = dfs(nxt, dst, visited)
                if sub != -1.0:
                    return w * sub         # multiply along the path
            return -1.0

        return [dfs(c, d, set()) for c, d in queries]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(Q * (V + E)): each query runs one DFS.
💾 Space Complexity
O(V + E) for the graph plus O(V) per DFS.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the reverse edge with the reciprocal weight: the graph must be traversable in both directions.
  • Dividing instead of multiplying along the path: A/C = (A/B) * (B/C).
  • Not checking whether the variables exist: an unknown variable must yield -1.0.
  • Reusing the visited set across queries: each query needs a fresh set.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems