Evaluating Division: Exploring Algorithms

Introduction

In this blog post, we will explore the problem of evaluating division. Given a set of equations and their corresponding values, we need to determine the result of evaluating a set of queries.

Problem Statement

Given a list of equations represented as pairs of strings equations, a corresponding list of values values, and a list of queries represented as pairs of strings queries, we need to find the result for each query. Each equation equations[i] = [A, B] and its corresponding value values[i] represents the division A / B, where A and B are variables and values[i] represents the result of the division.

Data Structure used

To solve this problem, we will use an unordered map to represent a graph. The graph will store the values of each equation, where the variables are the nodes and the values are the edges.

Algorithmic approach

Create an unordered map graph to represent the graph.
Iterate over the equations and values and populate the graph with the corresponding values. For each equation equations[i] = [A, B] and its value values[i], add an edge from A to B with the value values[i] and an edge from B to A with the value 1.0 / values[i].
Iterate over the queries and evaluate each query using a breadth-first search (BFS) approach.
- If either the start or end variable of the query is not present in the graph, skip the query.
- If the start and end variables of the query are the same, set the result to 1.0.
- Otherwise, perform a BFS starting from the start variable and keep track of the accumulated value so far.
  - If the current variable is the end variable of the query, set the result to the accumulated value multiplied by the edge value from the current variable to the end variable.
  - If the current variable has not been visited, enqueue it with the accumulated value multiplied by the edge value from the current variable to its neighbor and mark it as visited.
Return the results of the queries.

Implementation

vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, vector<vector<string>> &queries)
{
    unordered_map<string, unordered_map<string, double>> graph;
    int n = equations.size();
    for (int i = 0; i < n; ++i)
    {
        const string &numerator = equations[i][0];
        const string &denominator = equations[i][1];
        double value = values[i];

        graph[numerator][denominator] = value;
        graph[denominator][numerator] = 1.0 / value;
    }

    int m = queries.size();
    vector<double> results(m, -1.0);
    for (int i = 0; i < m; ++i)
    {
        const string &start = queries[i][0];
        const string &end = queries[i][1];

        if (graph.count(start) == 0 || graph.count(end) == 0)
        {
            continue;
        }

        if (start == end)
        {
            results[i] = 1.0;
            continue;
        }

        queue<pair<string, double>> q;
        unordered_set<string> visited;
        q.push({start, 1.0});
        visited.insert(start);

        while (!q.empty())
        {
            string current = q.front().first;
            double valueSoFar = q.front().second;
            q.pop();

            for (const auto &neighbor : graph[current])
            {
                const string &next = neighbor.first;
                double edgeValue = neighbor.second;

                if (next == end)
                {
                    results[i] = valueSoFar * edgeValue;
                    break;
                }

                if (visited.count(next) == 0)
                {
                    q.push({next, valueSoFar * edgeValue});
                    visited.insert(next);
                }
            }

            if (results[i] != -1.0)
            {
                break;
            }
        }
    }

    return results;
}

Time Complexity

The time complexity of this algorithm is O(V + E + Q), where V is the number of variables, E is the number of equations, and Q is the number of queries. Constructing the graph takes O(E) time, and processing each query takes O(V + E) time in the worst case, as it involves a BFS traversal. Thus, the overall time complexity is dominated by the BFS traversal.

Space Complexity

The space complexity of this algorithm is O(V + E), where V is the number of variables and E is the number of equations. The space is primarily used to store the graph, which requires O(V + E) space.

Conclusion

In this blog post, we discussed the problem of evaluating division. We explored an algorithmic approach that involves constructing a graph using an unordered map and performing a breadth-first search to evaluate the queries. This approach provides an efficient solution to the problem, with a time complexity of O(V + E + Q). By understanding the problem requirements and utilizing appropriate data structures and algorithms, we can efficiently solve such problems.

Links:

Stackable