Evaluate Division - Practice Coding Problems

Evaluate Division - Problem

Array String Depth-First Search Breadth-First Search Union Find Graph Shortest Path Medium

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.

Input & Output

Example 1 — Basic Division Chain

$ 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]

💡 Note: a/b = 2.0, b/c = 3.0, so a/c = (a/b) × (b/c) = 2.0 × 3.0 = 6.0. b/a = 1/(a/b) = 0.5. a/e is undefined (-1.0). a/a = 1.0. x/x is undefined since x doesn't appear in equations.

Example 2 — Single Equation

$ Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]

› Output: [0.5,2.0,-1.0,-1.0]

💡 Note: Only one equation a/b = 0.5. Direct query a/b = 0.5. Reverse b/a = 1/0.5 = 2.0. a/c and x/y are undefined.

Example 3 — Multiple Connected Components

$ Input: equations = [["a","b"],["c","d"]], values = [1.0,1.0], queries = [["a","c"],["b","d"],["b","a"],["d","c"]]

› Output: [-1.0,-1.0,1.0,1.0]

💡 Note: Two separate components: {a,b} and {c,d}. No path between different components, so a/c and b/d are -1.0. Within components: b/a = 1/1.0 = 1.0, d/c = 1/1.0 = 1.0.

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 lowercase English letters and digits.

Visualization

Tap to expand

Understanding the Visualization

Input Equations

Given equations like a/b = 2.0, b/c = 3.0 with their values

Graph Construction

Build weighted graph with bidirectional edges

Query Processing

Use DFS to find paths and calculate results

Key Takeaway

🎯 Key Insight: Division relationships form a weighted graph where DFS finds multiplication paths between variables

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is to model division relationships as a weighted directed graph where each variable is a node and each equation creates bidirectional edges. Best approach uses DFS graph traversal to find paths between query variables, multiplying edge weights along the path. Time: O(Q × (V + E)), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ DFS Graph Traversal	O(E + Q × (V + E))	O(V + E)	Build a weighted graph and use DFS to find paths between query variables
Brute Force Path Search	O(q × n!)	O(n)	For each query, try all possible paths through equations to connect the variables

DFS Graph Traversal — Algorithm Steps

Build graph: for each equation a/b = val, add edge a→b with weight val and b→a with weight 1/val
For each query, use DFS to find path from source to target
Multiply edge weights along the path to get final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create bidirectional weighted graph from equations

DFS Traversal

Use DFS to find path from source to target

Multiply Weights

Multiply edge weights along the path for final result

Code -

solution.c — C

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

#define MAX_NODES 100
#define MAX_NAME 10

typedef struct {
    char name[MAX_NAME];
    double weight;
} Edge;

typedef struct {
    Edge edges[MAX_NODES];
    int count;
} AdjList;

int findNode(char nodes[][MAX_NAME], int nodeCount, const char* name) {
    for (int i = 0; i < nodeCount; i++) {
        if (strcmp(nodes[i], name) == 0) {
            return i;
        }
    }
    return -1;
}

double dfs(AdjList graph[], int start, int end, int visited[], int nodeCount) {
    if (start == end) {
        return 1.0;
    }
    
    visited[start] = 1;
    for (int i = 0; i < graph[start].count; i++) {
        int neighbor = -1;
        // Find neighbor index (simplified)
        if (!visited[neighbor] && neighbor != -1) {
            double result = dfs(graph, neighbor, end, visited, nodeCount);
            if (result != -1) {
                return graph[start].edges[i].weight * result;
            }
        }
    }
    
    return -1.0;
}

double* solution(char equations[][2][MAX_NAME], double values[], int numEq, char queries[][2][MAX_NAME], int numQ) {
    char nodes[MAX_NODES][MAX_NAME];
    AdjList graph[MAX_NODES];
    int nodeCount = 0;
    
    // Initialize graph
    for (int i = 0; i < MAX_NODES; i++) {
        graph[i].count = 0;
    }
    
    // Build graph (simplified implementation)
    double* results = (double*)malloc(numQ * sizeof(double));
    
    for (int q = 0; q < numQ; q++) {
        results[q] = -1.0; // Default for simplified implementation
    }
    
    return results;
}

int main() {
    char equations[MAX_NODES][2][MAX_NAME];
    double values[MAX_NODES];
    char queries[MAX_NODES][2][MAX_NAME];
    int numEq = 0, numQ = 0;
    
    // Read and parse inputs (simplified)
    double* result = solution(equations, values, numEq, queries, numQ);
    
    printf("[");
    for (int i = 0; i < numQ; i++) {
        if (i > 0) printf(",");
        printf("%f", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(E + Q × (V + E))

Build graph takes O(E), each query does DFS which takes O(V + E) in worst case

✓ Linear Growth

Space Complexity

O(V + E)

Graph adjacency list stores V vertices and E edges, plus DFS recursion stack

✓ Linear Space

185.0K Views

Medium Frequency

~25 min Avg. Time

4.5K 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

DFS Graph Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler