Rakesh Reddy Peddamallu

Posted on Jul 30

399. Evaluate Division

#leetcode

🔍 Problem Overview

We are given equations like:

a / b = 2.0  
b / c = 3.0

And we’re asked queries like:

a / c = ?  
b / a = ?  
a / e = ?

Our goal is to evaluate each query based on the given equations.

💡 Key Idea – Think of it as a Graph

This problem is a classic graph traversal problem.

Treat each variable as a node in a graph.
For every equation a / b = 2.0, add:
- an edge a -> b with weight 2.0
- and b -> a with weight 1 / 2.0 = 0.5.

Once we build the graph, we use DFS (Depth-First Search) to find a path from the numerator to the denominator in each query and multiply the weights along the way.

🛠️ Step-by-Step Code Breakdown

var calcEquation = function(equations, values, queries) {
    const graph = {};

    // 1. Build the graph
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        const val = values[i];

        if (!graph[a]) graph[a] = [];
        if (!graph[b]) graph[b] = [];

        graph[a].push([b, val]);       // a -> b = val
        graph[b].push([a, 1 / val]);   // b -> a = 1/val
    }

    const result = [];

    // 2. Run DFS for each query
    for (const [start, end] of queries) {
        const visited = new Set();

        const dfs = (curr, target, accProduct) => {
            if (!graph[curr] || visited.has(curr)) return -1;
            if (curr === target) return accProduct;

            visited.add(curr);

            for (const [neighbor, weight] of graph[curr]) {
                const res = dfs(neighbor, target, accProduct * weight);
                if (res !== -1) return res;
            }

            return -1;
        };

        const value = dfs(start, end, 1.0);
        result.push(value);
    }

    return result;
};

🔍 Example Walkthrough

Given:

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

Graph looks like this:

a -> b (2.0)
b -> a (0.5)
b -> c (3.0)
c -> b (1/3.0)

Query: "a / c"

Path: a → b → c
Multiply weights: 2.0 * 3.0 = 6.0 ✅

⏱️ Time and Space Complexity

Time Complexity:

Building the graph: O(E) where E = number of equations
Each query can do DFS across all nodes: O(N)
Total = O(Q * N) where Q = number of queries, N = number of variables

Space Complexity:

Graph storage: O(E)
DFS visited set: O(N)

🧾 Final Thoughts

This problem shows how beautifully graph theory can solve real-world equation networks. By building a graph of relationships and searching for paths, we can compute complex ratios step-by-step.

If you see a question with variable relationships and divisions – think graph 🧠📈

DEV Community