Check for contradictions in equations

Array Depth-First Search Union-Find Graph Theory

43.8% acceptance

Mar 31, 2026

You are given a 2D array of strings equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] means that Ai / Bi = values[i]. Determine if there exists a contradiction in the equations. Return true if there is a contradiction, or false otherwise. Note: When checking if two numbers are equal, check that their absolute difference is less than 10-5. The testcases are generated such that there are no cases targeting precision, i.e. using double is enough to solve the problem.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn check_contradictions(equations: Vec<Vec<String>>, values: Vec<f64>) -> bool {
    // Build adjacency list: for a/b = v, add edges a->b with weight v and b->a with weight 1/v
    let mut map: HashMap<String, usize> = HashMap::new();
    let mut id = 0usize;
    for eq in &equations {
      for s in eq {
        if !map.contains_key(s) {
          map.insert(s.clone(), id);
          id += 1;
        }
      }
    }
    let n = id;
    let mut adj = vec![vec![]; n];
    for (i, eq) in equations.iter().enumerate() {
      let u = map[&eq[0]];
      let v = map[&eq[1]];
      adj[u].push((v, values[i]));
      adj[v].push((u, 1.0 / values[i]));
    }
    // BFS/DFS: assign weights and check consistency
    let mut weight = vec![0.0f64; n];
    let mut visited = vec![false; n];
    for start in 0..n {
      if visited[start] {
        continue;
      }
      weight[start] = 1.0;
      visited[start] = true;
      let mut queue = std::collections::VecDeque::new();
      queue.push_back(start);
      while let Some(u) = queue.pop_front() {
        for &(v, w) in &adj[u] {
          let expected = weight[u] * w;
          if visited[v] {
            if (weight[v] - expected).abs() / weight[v].max(expected).max(1e-9) > 1e-5 {
              return true;
            }
          } else {
            weight[v] = expected;
            visited[v] = true;
            queue.push_back(v);
          }
        }
      }
    }
    false
  }
}