LeetCode 399: Evaluate Division Solution Ascending Order Solution in Python – A Step-by-Step Guide

What Is LeetCode 399: Evaluate Division?

In LeetCode 399: Evaluate Division, you’re given three things: 1. A list of equations (like ["a/b", "b/c"]) with their values (like [2.0, 3.0]). 2. A list of queries (like ["a/c", "b/a"]). 3. Your job is to return an array of answers for each query (e.g., [6.0, 0.5]), or -1.0 if it’s impossible.

Each equation like a/b = 2.0 means a = 2.0 × b, and you can use these to figure out the queries. It’s like a chain of relationships—think of a as twice b, and b as three times c, so a must be six times c!

Problem Statement

• Input:
• equations: List of string pairs (e.g., ["a/b"]).
• values: List of floats (e.g., [2.0]).
• queries: List of string pairs to evaluate (e.g., ["a/c"]).
• Output: List of floats—results of each query or -1.0 if uncomputable.
• Rules:
• Use equations to compute queries.
• Variables are strings; values are positive floats.

Constraints

• 1 <= equations.length <= 20.
• Each equation has two different variables.
• 0.0 < values[i] <= 20.0.
• 1 <= queries.length <= 20.

Examples

• Input: equations = [["a/b","b/c"]], values = [2.0,3.0], queries = [["a/c","b/a","a/e","a/a","x/x"]]
• Output: [6.0, 0.5, -1.0, 1.0, -1.0].
• Input: equations = [["a/b"]], values = [0.5], queries = [["a/b","b/a","a/c","x/x"]]
• Output: [0.5, 2.0, -1.0, -1.0].

Understanding the Problem: Solving Division Chains

To solve LeetCode 399: Evaluate Division in Python, we need to take a bunch of division rules and answer questions about them. A brute-force way might be to try every combination, but that’s slow. Instead, we’ll use:

• Best Solution (Graph with DFS): O(Q × (N + E)) time (Q = queries, N = nodes, E = edges), O(N + E) space—models it as a graph.
• Alternative Solution (Union-Find with Weights): O((N + Q) × α(N)) time, O(N) space—groups variables with weights.

Let’s jump into the graph-based DFS solution with a clear, step-by-step explanation.

Best Solution: Graph with Depth-First Search (DFS)

Why This Is the Best Solution

The graph with DFS approach shines because it’s fast and makes sense—O(Q × (N + E)) time and O(N + E) space. It turns equations into a graph where variables are dots (nodes) and divisions are lines (edges) with weights. Then, it walks the graph to find answers. It’s like drawing a map of relationships and finding paths between points!

How It Works

Think of the equations as a treasure map:

• Step 1: Build the Map (Graph):
• Each variable (a, b, c) is a dot.
• Each equation (a/b = 2.0) is a line from a to b with weight 2.0, and b to a with weight 1/2.0 (the reverse).
• Step 2: Explore with DFS:
• For a query like a/c, start at a and search for a path to c.
• Multiply weights along the path (e.g., a → b → c: 2.0 × 3.0 = 6.0).
• Step 3: Handle No Path:
• If you can’t reach the end (like a to e), return -1.0.
• Step 4: Why This Works:
• The graph captures all relationships, including reverse ones (b/a = 1/2.0).
• DFS finds paths efficiently, multiplying weights as it goes.
• It’s like following a chain of clues to solve the puzzle!

Step-by-Step Example

Example: equations = [["a/b","b/c"]], values = [2.0,3.0], queries = [["a/c","b/a"]]

• Build the Graph:
• Nodes: a, b, c.
• Edges:
• a → b: 2.0, b → a: 0.5 (1/2.0).
• b → c: 3.0, c → b: 0.333 (1/3.0).
• Query "a/c":
• Start at a, go to b (×2.0), then b to c (×3.0).
• Result: 2.0 × 3.0 = 6.0.
• Query "b/a":
• Start at b, go to a (×0.5).
• Result: 0.5.
• Result: [6.0, 0.5].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Step 1: Build the graph
        graph = {}
        for (x, y), value in zip(equations, values):
            if x not in graph:
                graph[x] = {}
            if y not in graph:
                graph[y] = {}
            graph[x][y] = value          # x -> y with value
            graph[y][x] = 1.0 / value   # y -> x with reverse value

        # Step 2: DFS to find path and product
        def dfs(start, end, visited):
            # If start or end not in graph, no path
            if start not in graph or end not in graph:
                return -1.0
            # If start is end, result is 1.0
            if start == end:
                return 1.0
            visited.add(start)
            # Explore neighbors
            for neighbor, value in graph[start].items():
                if neighbor not in visited:
                    result = dfs(neighbor, end, visited)
                    if result != -1.0:
                        return value * result
            return -1.0

        # Step 3: Process each query
        results = []
        for start, end in queries:
            result = dfs(start, end, set())
            results.append(result)

        return results

• Line 4-11: Build the graph:
• graph is a dictionary of dictionaries: {node: {neighbor: weight}}.
• For each equation (x/y = v):
• Add x → y: v (e.g., a → b: 2.0).
• Add y → x: 1/v (e.g., b → a: 0.5).
• Line 14-26: DFS function:
• Line 16-17: If start or end isn’t in graph, return -1.0.
• Line 19-20: If start equals end, return 1.0 (e.g., a/a).
• Line 21: Mark start as visited.
• Line 22-26: Check each neighbor:
• If unvisited, recurse to find path to end.
• If path exists (not -1.0), multiply current weight and return.
• If no path, return -1.0.
• Line 29-33: Run queries:
• For each query, call DFS with fresh visited set, append result.
• Time Complexity: O(Q × (N + E))—Q queries, each DFS explores nodes (N) and edges (E).
• Space Complexity: O(N + E)—graph storage.

This is like a treasure hunt through a map of divisions!

Alternative Solution: Union-Find with Weights

Why an Alternative Approach?

The union-find with weights method groups variables into sets and tracks division ratios between them. It’s O((N + Q) × α(N)) time (α is nearly constant) and O(N) space—different but still solid. It’s like organizing variables into families with conversion rates!

How It Works

Picture it as family trees:

• Step 1: Each variable starts alone with parent as itself and weight 1.0.
• Step 2: For each equation (a/b = v):
• Union a and b, set weight ratios (a to root, b to root).
• Step 3: For a query a/b:
• Find roots of a and b.
• If same root, compute ratio; else, -1.0.

Step-by-Step Example

Example: equations = [["a/b"]], values = [2.0], queries = [["a/b"]]

• Union: a and b in one set, a/b = 2.0.
• Query "a/b": Same set, ratio = 2.0.
• Result: [2.0].

Code for Union-Find Approach

Copy codeclass Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Parent and weight for each node
        parent = {}
        weight = {}

        def find(x):
            if x not in parent:
                parent[x] = x
                weight[x] = 1.0
            if parent[x] != x:
                root = find(parent[x])
                weight[x] *= weight[parent[x]]
                parent[x] = root
            return parent[x]

        def union(x, y, value):
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                parent[root_x] = root_y
                weight[root_x] = value * weight[y] / weight[x]

        # Build the union-find structure
        for (x, y), value in zip(equations, values):
            union(x, y, value)

        # Process queries
        results = []
        for x, y in queries:
            if x in parent and y in parent and find(x) == find(y):
                results.append(weight[x] / weight[y])
            else:
                results.append(-1.0)

        return results

• Time Complexity: O((N + Q) × α(N))—union and find operations.
• Space Complexity: O(N)—parent and weight storage.

It’s a family reunion with division rules!

Comparing the Two Solutions

• Graph with DFS (Best):
• Pros: O(Q × (N + E)), O(N + E), intuitive graph.
• Cons: More complex to set up.
• Union-Find (Alternative):
• Pros: O((N + Q) × α(N)), O(N), unique approach.
• Cons: Less intuitive.

Graph wins for clarity.

Additional Examples and Edge Cases

• [["a/b"],["b/c"],["c/d"]], [1.0,2.0,3.0], ["a/d"]: 6.0.
• [["a/b"]], [2.0], ["c/d"]: -1.0.

Graph handles all.

Complexity Breakdown

• Graph DFS: Time O(Q × (N + E)), Space O(N + E).
• Union-Find: Time O((N + Q) × α(N)), Space O(N).

Graph’s practical.

Key Takeaways

• Graph DFS: Map and search!
• Union-Find: Group and weigh!
• Equations: Chains are fun.
• Python Tip: Dicts are key—see [Python Basics](/python/basics).

Final Thoughts: Solve the Division Puzzle

LeetCode 399: Evaluate Division in Python is a relationship-solving quest. Graph with DFS maps it out fast, while union-find groups it up. Want more graph fun? Try LeetCode 207: Course Schedule or LeetCode 547: Number of Provinces. Ready to divide? Head to Solve LeetCode 399 on LeetCode and crack those equations today!