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

Problem Statement:

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.

 

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

 

Constraints:

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj consist of lower case English letters and digits.

Solution:

In BFS and DFS, the idea is to traverse the graph and at each node, keep track of the conversion factor. In DSU, the idea is to separately maintain the conversion factor with respect to the root for each node. What this means is that in DFS and BFS we will have to do traversal for each query separately, but in DSU, we can just look up the answer from a hashamp.

DFS solution:

 
class Solution {
public:
    double dfs(unordered_map<string, vector<pair<string,double>>>&G, unordered_set<string>&visited, \
                string source, string target, double factor)
    {
        if (source==target) return factor;
        for (auto &nbd: G[source]) if (!visited.count(nbd.first))
        {
            visited.insert(nbd.first);
            double res = dfs(G,visited,nbd.first,target,factor*nbd.second);
            if (res!=-1) return res;
        }
        return -1;
    }
    double solveQuery(unordered_map<string, vector<pair<string,double>>> &G, string c, string d)
    {
        unordered_set<string> visited;
        visited.insert(c);
        return dfs(G, visited, c, d, 1);
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) 
    {
        int n = equations.size();
        unordered_map<string, vector<pair<string,double>>> G;
        for (int i=0; i<n; i++)
        {
            string a=equations[i][0], b=equations[i][1];
            double v=values[i];
            G[a].push_back({b, v});
            G[b].push_back({a, 1/v});
        }
        vector<double> res(queries.size());
        for (int i=0; i<queries.size(); i++)
        {
            string c = queries[i][0], d=queries[i][1];
            if (!G.count(c) || !G.count(d)) res[i]=-1;
            else res[i] = solveQuery(G, queries[i][0], queries[i][1]);
        }            
        return res;
    }
};

BFS solution:

 
class Solution {
public:
    double solveQuery(unordered_map<string, vector<pair<string,double>>> &G, string c, string d)
    {
        queue<pair<string,double>>Q;
        unordered_set<string> visited;
        Q.push({c,1});
        visited.insert(c);
        while(!Q.empty())
        {
            for (int i=Q.size(); i>0; i--)
            {
                auto pair = Q.front();
                Q.pop();
                string cur=pair.first;
                double val=pair.second;
                if (cur==d) return val;
                for (auto nbd: G[cur]) if (!visited.count(nbd.first))
                {
                    if (nbd.first==d) return val*nbd.second;
                    visited.insert(nbd.first);
                    Q.push({nbd.first, val*nbd.second});
                }
            }
        }
        return -1;
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) 
    {
        int n = equations.size();
        unordered_map<string, vector<pair<string,double>>> G;
        for (int i=0; i<n; i++)
        {
            string a=equations[i][0], b=equations[i][1];
            double v=values[i];
            G[a].push_back({b, v});
            G[b].push_back({a, 1/v});
        }
        vector<double> res(queries.size());
        for (int i=0; i<queries.size(); i++)
        {
            string c = queries[i][0], d=queries[i][1];
            if (!G.count(c) || !G.count(d)) res[i]=-1;
            else res[i] = solveQuery(G, queries[i][0], queries[i][1]);
        }            
        return res;
    }
};

DSU solution: In the find opration, we return the conversion factor with respect to the root node along with the value of the root node. In the union operation, I am illustrating with an example. Let $x$ and $y$ be two nodes with roots $R_x$ and $R_y$ respectively. We have the conversion factors $x=r_1R_x$ and $y=r_2R_y$ with respect to the respective root nodes. Now we get the equation $x=ry$. We must set the conversion rate of $R_y$ wrt $R_x$ now. We have $x=r_1R_x, y=r_2R_y, x=ry$. We can solve to get $R_y = \frac{r_1}{rr_2}R_x$.

 
class UnionFind
{
public:
    unordered_map<string, string> roots;
    unordered_map<string, int> ranks;
    unordered_map<string, double> rates;
    UnionFind(unordered_set<string> &nodes)
    {
        for (string node: nodes)
        {
            roots[node] = node;
            ranks[node] = 1;
            rates[node] = 1;
        }
    }
    void unionSet(string x, string y, double rate)
    {
        auto pairX = find(x), pairY = find(y);
        string rootX = pairX.first, rootY = pairY.first;
        double rateX = pairX.second, rateY = pairY.second;
        if (rootX==rootY) return;
        if (ranks[rootX]==ranks[rootY]) ranks[rootX]++;
        if (ranks[rootX] <ranks[rootY])
        {
            swap(rootX, rootY);
            swap(rateX, rateY);
            rate = 1/rate;
        }
        roots[rootY] = rootX;
        //x=r1Rx, y=r2Ry, x=ry, r1Rx=r(r2Ry), Ry=(r1/(rr2))Rx
        rates[rootY] =  rateX / rateY / rate;
    }
    pair<string,double> find(string x)
    {
        if (x==roots[x]) return {x, rates[x]};
        auto pair = find(roots[x]);
        roots[x] = pair.first;
        rates[x] *= pair.second;
        return {roots[x], rates[x]};
    }
    double conversionFactor(string x, string y)
    {
        auto pairX = find(x), pairY = find(y);
        string rootX = pairX.first, rootY = pairY.first;
        double rateX = pairX.second, rateY = pairY.second;
        if (rootX!=rootY) return -1;
        return rateX/rateY;
    }
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, \
                                vector<vector<string>>& queries) 
    {
        unordered_set<string> nodes;
        for (auto &eqn: equations){nodes.insert(eqn[0]); nodes.insert(eqn[1]);}
        UnionFind uf = UnionFind(nodes);
        for (int i=0; i<equations.size(); i++)
        {
            string a = equations[i][0];
            string b = equations[i][1];
            double v = values[i];
            uf.unionSet(a, b, v);
        }
        vector<double> res;
        for (auto &query: queries)
        {
            string c = query[0], d=query[1];
            if (!nodes.count(c) || !nodes.count(d)) res.push_back(-1);
            else res.push_back(uf.conversionFactor(c, d));
        }
        return res;
    }
};