LeetCode #399 — MEDIUM

Evaluate Division

Move from brute-force thinking to an efficient approach using array strategy.

The Problem

Problem Statement

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

You are also given some queries, where queries[j] = [C_j, D_j] represents the j^th query where you must find the answer for C_j / D_j = ?.

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.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= A_i.length, B_i.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= C_j.length, D_j.length <= 5
A_i, B_i, C_j, D_j consist of lower case English letters and digits.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Union-Find

Example 1

[["a","b"],["b","c"]]
[2.0,3.0]
[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

Example 2

[["a","b"],["b","c"],["bc","cd"]]
[1.5,2.5,5.0]
[["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

Example 3

[["a","b"]]
[0.5]
[["a","b"],["b","a"],["a","c"],["x","y"]]

Core Insight

What unlocks the optimal approach

Do you recognize this as a graph problem?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #399: Evaluate Division
class Solution {
    private Map<String, String> p;
    private Map<String, Double> w;

    public double[] calcEquation(
        List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n = equations.size();
        p = new HashMap<>();
        w = new HashMap<>();
        for (List<String> e : equations) {
            p.put(e.get(0), e.get(0));
            p.put(e.get(1), e.get(1));
            w.put(e.get(0), 1.0);
            w.put(e.get(1), 1.0);
        }
        for (int i = 0; i < n; ++i) {
            List<String> e = equations.get(i);
            String a = e.get(0), b = e.get(1);
            String pa = find(a), pb = find(b);
            if (Objects.equals(pa, pb)) {
                continue;
            }
            p.put(pa, pb);
            w.put(pa, w.get(b) * values[i] / w.get(a));
        }
        int m = queries.size();
        double[] ans = new double[m];
        for (int i = 0; i < m; ++i) {
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            ans[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d))
                ? -1.0
                : w.get(c) / w.get(d);
        }
        return ans;
    }

    private String find(String x) {
        if (!Objects.equals(p.get(x), x)) {
            String origin = p.get(x);
            p.put(x, find(p.get(x)));
            w.put(x, w.get(x) * w.get(origin));
        }
        return p.get(x);
    }
}

// Accepted solution for LeetCode #399: Evaluate Division
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	p := make(map[string]string)
	w := make(map[string]float64)
	for _, e := range equations {
		a, b := e[0], e[1]
		p[a], p[b] = a, b
		w[a], w[b] = 1.0, 1.0
	}

	var find func(x string) string
	find = func(x string) string {
		if p[x] != x {
			origin := p[x]
			p[x] = find(p[x])
			w[x] *= w[origin]
		}
		return p[x]
	}

	for i, v := range values {
		a, b := equations[i][0], equations[i][1]
		pa, pb := find(a), find(b)
		if pa == pb {
			continue
		}
		p[pa] = pb
		w[pa] = w[b] * v / w[a]
	}
	var ans []float64
	for _, e := range queries {
		c, d := e[0], e[1]
		if p[c] == "" || p[d] == "" || find(c) != find(d) {
			ans = append(ans, -1.0)
		} else {
			ans = append(ans, w[c]/w[d])
		}
	}
	return ans
}

# Accepted solution for LeetCode #399: Evaluate Division
class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[float], queries: List[List[str]]
    ) -> List[float]:
        def find(x):
            if p[x] != x:
                origin = p[x]
                p[x] = find(p[x])
                w[x] *= w[origin]
            return p[x]

        w = defaultdict(lambda: 1)
        p = defaultdict()
        for a, b in equations:
            p[a], p[b] = a, b
        for i, v in enumerate(values):
            a, b = equations[i]
            pa, pb = find(a), find(b)
            if pa == pb:
                continue
            p[pa] = pb
            w[pa] = w[b] * v / w[a]
        return [
            -1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d]
            for c, d in queries
        ]

// Accepted solution for LeetCode #399: Evaluate Division
use std::collections::HashMap;

#[derive(Debug)]
pub struct DSUNode {
    parent: String,
    weight: f64,
}

pub struct DisjointSetUnion {
    nodes: HashMap<String, DSUNode>,
}

impl DisjointSetUnion {
    pub fn new(equations: &Vec<Vec<String>>) -> DisjointSetUnion {
        let mut nodes = HashMap::new();
        for equation in equations.iter() {
            for iter in equation.iter() {
                nodes.insert(
                    iter.clone(),
                    DSUNode {
                        parent: iter.clone(),
                        weight: 1.0,
                    },
                );
            }
        }
        DisjointSetUnion { nodes }
    }

    pub fn find(&mut self, v: &String) -> String {
        let origin = self.nodes[v].parent.clone();
        if origin == *v {
            return origin;
        }

        let root = self.find(&origin);
        self.nodes.get_mut(v).unwrap().parent = root.clone();
        self.nodes.get_mut(v).unwrap().weight *= self.nodes[&origin].weight;
        root
    }

    pub fn union(&mut self, a: &String, b: &String, v: f64) {
        let pa = self.find(a);
        let pb = self.find(b);
        if pa == pb {
            return;
        }
        let (wa, wb) = (self.nodes[a].weight, self.nodes[b].weight);
        self.nodes.get_mut(&pa).unwrap().parent = pb;
        self.nodes.get_mut(&pa).unwrap().weight = (wb * v) / wa;
    }

    pub fn exist(&mut self, k: &String) -> bool {
        self.nodes.contains_key(k)
    }

    pub fn calc_value(&mut self, a: &String, b: &String) -> f64 {
        if !self.exist(a) || !self.exist(b) || self.find(a) != self.find(b) {
            -1.0
        } else {
            let wa = self.nodes[a].weight;
            let wb = self.nodes[b].weight;
            wa / wb
        }
    }
}

impl Solution {
    pub fn calc_equation(
        equations: Vec<Vec<String>>,
        values: Vec<f64>,
        queries: Vec<Vec<String>>,
    ) -> Vec<f64> {
        let mut dsu = DisjointSetUnion::new(&equations);
        for (i, &v) in values.iter().enumerate() {
            let (a, b) = (&equations[i][0], &equations[i][1]);
            dsu.union(a, b, v);
        }

        let mut ans = vec![];
        for querie in queries {
            let (c, d) = (&querie[0], &querie[1]);
            ans.push(dsu.calc_value(c, d));
        }
        ans
    }
}

// Accepted solution for LeetCode #399: Evaluate Division
function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    const g: Record<string, [string, number][]> = {};
    const ans = Array.from({ length: queries.length }, () => -1);

    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        (g[a] ??= []).push([b, values[i]]);
        (g[b] ??= []).push([a, 1 / values[i]]);
    }

    for (let i = 0; i < queries.length; i++) {
        const [c, d] = queries[i];
        const vis = new Set<string>();
        const q: [string, number][] = [[c, 1]];

        if (!g[c] || !g[d]) continue;
        if (c === d) {
            ans[i] = 1;
            continue;
        }

        for (const [current, v] of q) {
            if (vis.has(current)) continue;
            vis.add(current);

            for (const [intermediate, multiplier] of g[current]) {
                if (vis.has(intermediate)) continue;

                if (intermediate === d) {
                    ans[i] = v * multiplier;
                    break;
                }

                q.push([intermediate, v * multiplier]);
            }

            if (ans[i] !== -1) break;
        }
    }

    return ans;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(α(n))

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(n) space

Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.

UNION-FIND

O(α(n)) time

O(n) space

With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.

Shortcut: Union-Find with path compression + rank → O(α(n)) per operation ≈ O(1). Just say “nearly constant.”

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.