Posts Evaluate Division
Post
Cancel

Evaluate Division

PROBLEM DESCRIPTION

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.

leetcode

SOLUTION

The important observation is that, if the value from A -> B is x, then the value from B -> A will be 1/x. Also, if A -> B is x and B -> C is y, then A -> C will be x multiplied by y. To solve this we can therefore create a directed graph and use BFS from source to destination while keeping the current value which needs to be multiplied based on the “weight” of that edge from source to destination.

Another small thing to take care of in this problem is that the String AB and BA mean the same key. So, we can store the sorted value of that string while using the directed weighted graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Solution {
    
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        // Build directed graph
        //A -> B with weight from values[]
        //B -> A with 1/weight
        Map<String, List<Pair>> graph = new HashMap<>();

        // Populate the graph with given equations and values
        for (int i = 0; i < equations.size(); i++) {
            String x = sorted(equations.get(i).get(0));  // Source variable
            String y = sorted(equations.get(i).get(1));  // Destination variable
            double val = values[i];  // Value of the equation

            // Add the edge from x to y with weight val
            graph.computeIfAbsent(x, k -> new ArrayList<>()).add(new Pair(y, val));

            // Add the edge from y to x with weight 1/val
            graph.computeIfAbsent(y, k -> new ArrayList<>()).add(new Pair(x, 1.0 / val));
        }

        // Array to store results for each query
        double[] ans = new double[queries.size()];

        // Evaluate each query
        for (int i = 0; i < queries.size(); i++) {
            ans[i] = calculateValue(graph, sorted(queries.get(i).get(0)), sorted(queries.get(i).get(1)), 1.0, new HashSet<String>());
        }

        return ans;
    }

    // Recursive function to calculate the value of a query
    public double calculateValue(Map<String, List<Pair>> graph, String source, String destination, double total, Set<String> visited) {

        // If we've already visited this node -1
        if (visited.contains(source)) return -1.0;

        // If the source or destination node is not in the graph, return -1.0
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            return -1.0;
        }

        // Get the neighbors of the current source node
        List<Pair> neighbors = graph.get(source);

        // Iterate through neighbors to find a valid path
        for (Pair p : neighbors) {

            String d = p.destination;  // Neighbor destination
            double w = p.weight;       // Weight of the edge

            // If we've reached the destination, return the calculated value
            if (d.equals(destination)) {
                return total * w;
            }

            // Mark the current source as visited
            visited.add(source);

            // Recurse to find a path from the neighbor to the destination
            double result = calculateValue(graph, d, destination, total * w, visited);

            // If a valid result is found, return it
            if (result != -1.0) {
                return result;
            }
        }

        // No valid path found, return -1.0
        return -1.0;
    }

    // Method to sort characters in a string and return the sorted result
    public static String sorted(String input) {
        char[] charArray = input.toCharArray();
        java.util.Arrays.sort(charArray);
        return new String(charArray);
    }

}

// Class to represent an edge (pair) in the graph
class Pair {

    String destination;
    double weight;

    Pair(String destination, double weight){
        this.destination = destination;
        this.weight = weight;
    }

}

This post is licensed under CC BY 4.0 by the author.