Check for Contradictions in Equations - Practice Coding Problems

Check for Contradictions in Equations - Problem

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.

Input & Output

Example 1 — No Contradiction

$ Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0]

› Output: false

💡 Note: We have a/b = 2.0 and b/c = 3.0, which gives a/c = 6.0. No contradictory equations exist.

Example 2 — Direct Contradiction

$ Input: equations = [["a","b"],["a","b"]], values = [2.0,3.0]

› Output: true

💡 Note: Same equation a/b appears twice with different values (2.0 and 3.0), which is a contradiction.

Example 3 — Indirect Contradiction

$ Input: equations = [["a","b"],["b","c"],["a","c"]], values = [2.0,3.0,5.0]

› Output: true

💡 Note: We have a/b = 2.0 and b/c = 3.0, so a/c should be 6.0, but the direct equation gives a/c = 5.0.

Constraints

1 ≤ equations.length ≤ 500
equations[i].length == 2
1 ≤ equations[i][j].length ≤ 5
values[i] > 0.0
1 ≤ values.length ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input

Equations define ratios between variables

Process

Build graph and check for contradictory paths

Output

Return true if contradiction found, false otherwise

Key Takeaway

🎯 Key Insight: Model equations as a weighted graph and detect contradictory paths using graph traversal algorithms

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to model equations as a weighted graph where variables are nodes and ratios are edge weights. Build the graph and use DFS to detect contradictory paths between variables. Best approach is DFS Graph Traversal with Time: O(V²), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Path Checking	O(n³)	O(n²)	Check all possible equation combinations for contradictions
DFS Graph Traversal	O(V²)	O(V + E)	Build graph and use DFS to detect contradictory paths

Brute Force Path Checking — Algorithm Steps

Build all direct ratios from equations
For each variable pair, calculate ratio through all possible paths
Check if any path gives contradictory results

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency map with division ratios

Check Paths

Compare direct vs indirect paths between all variable pairs

Detect Contradiction

Return true if any path gives inconsistent ratios

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

bool solution(char equations[][2][10], double* values, int n) {
    // Simplified implementation for basic contradiction detection
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Check if same equation with different value
            if (strcmp(equations[i][0], equations[j][0]) == 0 && 
                strcmp(equations[i][1], equations[j][1]) == 0) {
                if (fabs(values[i] - values[j]) > 1e-5) {
                    return true;
                }
            }
            // Check reverse equation
            if (strcmp(equations[i][0], equations[j][1]) == 0 && 
                strcmp(equations[i][1], equations[j][0]) == 0) {
                if (fabs(values[i] * values[j] - 1.0) > 1e-5) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    char equations[100][2][10];
    double values[100];
    int n = 1;
    
    // Simplified input parsing
    strcpy(equations[0][0], "a");
    strcpy(equations[0][1], "b");
    values[0] = 2.0;
    
    bool result = solution(equations, values, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each pair of variables, we may need to check all possible paths

⚠ Quadratic Growth

Space Complexity

O(n²)

Store all variable relationships in a map

⚠ Quadratic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Path Checking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler