Leetcode 399. Evaluate Division

Jimmy   Feb 25, 2025   1324 words   ~35 mins
#Array #String #Depth-First Search #Breadth-First Search #Union Find #Graph #Shortest Path

Table of Contents

Problem Informations

  • Problem Index: 399
  • Problem Link: Evaluate Division
  • Topics: Array, String, Depth-First Search, Breadth-First Search, Union Find, Graph, Shortest Path

Problem Description

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.

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 ]
note: x is undefined => -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 \leq equations.length \leq 20$
  • $equations[i].length == 2$
  • $1 \leq A_i.length, B_i.length \leq 5$
  • $values.length == equations.length$
  • $0.0 < values[i] \leq 20.0$
  • $1 \leq queries.length \leq 20$
  • $queries[i].length == 2$
  • $1 \leq C_j.length, D_j.length \leq 5$
  • $A_i, B_i, C_j, D_j$ consist of lower case English letters and digits.

Intuition

The problem involves evaluating division expressions based on a system of equations. The equations are given as pairs of variables with an associated value indicating the result of dividing the first variable by the second. Queries ask for the result of certain divisions. This problem can be effectively tackled by representing it as a graph problem, where variables are nodes and divisions are weighted edges. The Floyd-Warshall algorithm is well-suited for this task, as it computes the shortest paths between all pairs of nodes, allowing us to determine the division result for any pair of variables based on transitive relationships.

Approach

The approach begins by mapping each unique variable to an index to form a graph where nodes represent variables. We utilize an adjacency matrix, grid, to store division results between variables as edge weights. Initializing the grid, we populate it according to given equations and their respective values. We assign grid positions to account for both forward and reverse relationships (i.e., $A / B$ and $B / A$) by setting corresponding matrix values.

For this problem:

  1. First, we assign a unique index to each variable using a map.
  2. We create a square matrix grid where grid[i][j] initially holds a large value (representing infinity), signifying no known direct relationship.
  3. We populate the grid with known division results and their reciprocals from the input:
    • For each equation $A_i / B_i = \text{value}_i$, update the corresponding values in grid.
    • We also set grid[i][i] to 1 for all $i$, representing $A / A = 1$.
  4. We apply the Floyd-Warshall algorithm to compute potential paths through the graph. This involves iterating over all possible intermediate nodes k and attempting to find shorter paths (or valid connections) between nodes i and j using k as a mediator. Specifically, for each triple of nodes (i, k, j), if a path exists from i to k and from k to j, we update grid[i][j] with the product grid[i][k] * grid[k][j] if grid[i][j] was previously unknown.
  5. Once the grid is fully populated, queries are answered by directly retrieving the value grid[i][j] for the queried pair (C, D). If either variable is not found in our initial mapping or if grid[i][j] remains infinity, it indicates that the division cannot be computed, and we return -1.0.

This solution efficiently addresses queries by leveraging pre-computed transitive relations, allowing for constant time lookups for each query after the preparation phase.

Code

C++

#include <vector>
#include <string>
#include <map>
#define MAX 500

class Solution {
public:
    std::vector<double> calcEquation(std::vector<std::vector<std::string>>& equations, 
                                     std::vector<double>& values, 
                                     std::vector<std::vector<std::string>>& queries) {
        int elementIndex = 0;
        std::map<std::string, int> elementMap;

        // Assign a unique index to each variable in the equations
        for (int i = 0; i < equations.size(); ++i) {
            if (elementMap.find(equations[i][0]) == elementMap.end()) {
                elementMap[equations[i][0]] = elementIndex++;
            }
            if (elementMap.find(equations[i][1]) == elementMap.end()) {
                elementMap[equations[i][1]] = elementIndex++;
            }
        }
        
        // Initialize a grid to store the direct division results
        std::vector<std::vector<double>> grid(elementMap.size(), std::vector<double>(elementMap.size(), MAX));

        // Populate the grid with known values from the given equations
        for (int i = 0; i < equations.size(); ++i) {
            grid[elementMap[equations[i][0]]][elementMap[equations[i][1]]] = values[i];
            grid[elementMap[equations[i][1]]][elementMap[equations[i][0]]] = 1.0 / values[i];
        }
        
        // Set the division of any variable by itself to be 1
        for (int i = 0; i < elementMap.size(); ++i) {
            grid[i][i] = 1.0;
        }

        // Apply the Floyd-Warshall algorithm to find all pairs shortest paths
        for (int k = 0; k < elementMap.size(); ++k) {
            for (int i = 0; i < elementMap.size(); ++i) {
                if (grid[i][k] == MAX) continue;
                for (int j = 0; j < elementMap.size(); ++j) {
                    if (grid[k][j] == MAX || grid[i][j] != MAX) continue;
                    grid[i][j] = grid[i][k] * grid[k][j];
                }
            }
        }

        // Answer each query
        std::vector<double> answers(queries.size());
        for (int i = 0; i < queries.size(); ++i) {
            if (elementMap.find(queries[i][0]) == elementMap.end() || 
                elementMap.find(queries[i][1]) == elementMap.end() || 
                grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]] == MAX) {
                answers[i] = -1.0; // if query cannot be resolved, return -1.0
            } else {
                answers[i] = grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]];
            }
        }

        return answers;
    }
};

Python

class Solution:
    def calcEquation(self, equations, values, queries):
        elementIndex = 0
        elementMap = {}

        # Assign a unique index to each variable in the equations
        for i in range(len(equations)):
            if equations[i][0] not in elementMap:
                elementMap[equations[i][0]] = elementIndex
                elementIndex += 1
            if equations[i][1] not in elementMap:
                elementMap[equations[i][1]] = elementIndex
                elementIndex += 1
        
        # Initialize a grid to store the direct division results
        grid = [[float('inf')] * len(elementMap) for _ in range(len(elementMap))]
        
        # Populate the grid with known values from the given equations
        for i in range(len(equations)):
            grid[elementMap[equations[i][0]]][elementMap[equations[i][1]]] = values[i]
            grid[elementMap[equations[i][1]]][elementMap[equations[i][0]]] = 1.0 / values[i]
        
        # Set the division of any variable by itself to be 1
        for i in range(len(elementMap)):
            grid[i][i] = 1.0

        # Apply the Floyd-Warshall algorithm to find all pairs shortest paths
        for k in range(len(elementMap)):
            for i in range(len(elementMap)):
                if grid[i][k] == float('inf'):
                    continue
                for j in range(len(elementMap)):
                    if grid[k][j] == float('inf') or grid[i][j] != float('inf'):
                        continue
                    grid[i][j] = grid[i][k] * grid[k][j]

        # Answer each query
        answers = [0.0] * len(queries)
        for i in range(len(queries)):
            if (queries[i][0] not in elementMap or 
                queries[i][1] not in elementMap or 
                grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]] == float('inf')):
                answers[i] = -1.0 # if query cannot be resolved, return -1.0
            else:
                answers[i] = grid[elementMap[queries[i][0]]][elementMap[queries[i][1]]]
        
        return answers

Complexity

  • Time complexity: The algorithm uses a modified Floyd-Warshall approach to compute the results, which has a time complexity of $O(n^3)$. Here, $n$ is the number of distinct variables, which is determined by the number of unique elements in the equations array. Assigning indices to each variable takes $O(e)$ time, where $e$ is the number of equations. Constructing the initial grid takes $O(e)$ time. The Floyd-Warshall algorithm then processes this grid in $O(n^3)$ time. Finally, each query is resolved in constant time $O(1)$, and thus the queries take $O(q)$ time, where $q$ is the number of queries. Consequently, the overall time complexity is $O(e + n^3 + q)$, which simplifies to $O(n^3)$ given the constraints (where $n \leq 40$ at most, as deduced from constraints).

  • Space complexity: The space complexity of this solution is $O(n^2)$ due to the storage of the grid that maps all possible direct division results between the variables. Additionally, storing the mapping of variables to indices also takes $O(n)$ space. Therefore, the total space complexity is dominated by $O(n^2)$.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.