algoadvance

Leetcode 399. Evaluate Division

Problem Statement

You are given equations in the form of A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Example:

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]

Clarifying Questions

  1. Are all values guaranteed to be positive or can they be negative/zero?
    • All values are guaranteed to be positive since it’s a division and the input is valid.
  2. Can variable names have special characters, or are they strictly alphabetic strings?
    • The problem constraints don’t specify this detail, but we can assume that variable names are valid strings without special constraints.
  3. What is the maximum size of the equations and queries?
    • This is not specified in the problem statement. We will implement a solution that is efficient for typical constraints, but it may need further optimization for extremely large inputs.

Strategy

To solve this problem, we will treat it as a graph traversal problem where variables are nodes and equations provide edges with weights:

  1. Graph Representation:
    • Use an adjacency list to represent the graph. Each node will have connections to other nodes with corresponding weights (quotients).
  2. Build the Graph:
    • For each equation A/B = k, add edges A -> B with weight k and B -> A with weight 1/k.
  3. Graph Traversal for Queries:
    • Use Depth First Search (DFS) to evaluate each query. Start from the queried variable and attempt to reach the target variable, accumulating the product of weights along the path.
    • If the target is reachable, the traversal will result in the correct answer. If not, return -1.0.

Code

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    unordered_map<string, unordered_map<string, double>> graph;

    void addEdge(string from, string to, double value) {
        graph[from][to] = value;
        graph[to][from] = 1.0 / value;
    }

    bool dfs(const string &cur, const string &target, unordered_set<string> &visited, double &value) {
        // If we have found the target
        if (graph[cur].find(target) != graph[cur].end()) {
            value *= graph[cur][target];
            return true;
        }
        
        // Mark current node as visited
        visited.insert(cur);

        for (const auto &neighbor : graph[cur]) {
            if (visited.find(neighbor.first) == visited.end()) {
                double temp = value * neighbor.second;
                
                if (dfs(neighbor.first, target, visited, temp)) {
                    // If target found during DFS, propagate the result upward
                    value = temp;
                    return true;
                }
            }
        }

        // Target was not reachable from this path
        return false;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // Build the graph
        for (int i = 0; i < equations.size(); ++i) {
            addEdge(equations[i][0], equations[i][1], values[i]);
        }

        vector<double> results;

        // Process each query
        for (const auto &query : queries) {
            string from = query[0];
            string to = query[1];

            // If either node doesn’t exist in the graph
            if (graph.find(from) == graph.end() || graph.find(to) == graph.end()) {
                results.push_back(-1.0);
            } else {
                unordered_set<string> visited;
                double value = 1.0;
                results.push_back(dfs(from, to, visited, value) ? value : -1.0);
            }
        }

        return results;
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI