SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a list of equations and their respective values, the task is to evaluate queries using the equations. Each equation is in the form A / B = k, where A and B are variables represented as strings, and k is a real number. Given some queries, return the result of each query. If the answer does not exist, return -1.0.

Intuition

The problem can be visualized as a graph traversal problem where each equation represents a directed edge with a weight. The variables are nodes, and the values represent the edge weights between these nodes. To find the result of a query, we can perform a depth-first search (DFS) to find a path from the source variable to the target variable, multiplying the weights along the path.

Approach

1. Graph Construction:

   • Build a graph where each node represents a variable, and each directed edge represents the division relationship between the variables.
   • Use an adjacency list to represent the graph, where graph[a][b] is the value of a / b.

2. Depth-First Search (DFS):

   • For each query, use DFS to search for a path from the source variable to the target variable.
   • Keep track of visited nodes to avoid cycles.
   • If a path is found, multiply the edge weights along the path to get the result.
   • If no path is found, return -1.0.

3. Processing Queries:

   • Iterate through the list of queries and perform the DFS for each query to get the result.

Complexity

Time Complexity:

• Building the graph takes O(E), where E is the number of equations.
• Each DFS traversal takes O(V + E), where V is the number of variables (nodes) and E is the number of relationships (edges).
• For Q queries, the total time complexity is O(Q * (V + E)).

Space Complexity:

• The graph's space complexity is O(V + E).
• The space for the recursion stack in DFS is O(V).
• Overall space complexity is O(V + E).

Code

C++

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;
        // Build the graph
        for (int i = 0; i < equations.size(); i++) {
            const string& a = equations[i][0];
            const string& b = equations[i][1];
            double value = values[i];
            graph[a][b] = value;
            graph[b][a] = 1.0 / value;
        }
        // Function to perform DFS
        function<double(const string&, const string&, unordered_set<string>&)> dfs = [&](const string& src, const string& target, unordered_set<string>& seen) -> double {
            if (graph.find(src) == graph.end() || graph.find(target) == graph.end()) {
                return -1.0;
            }
            if (src == target) {
                return 1.0;
            }
            seen.insert(src);
            for (const auto& neighbor : graph[src]) {
                if (seen.find(neighbor.first) != seen.end()) {
                    continue;
                }
                double result = dfs(neighbor.first, target, seen);
                if (result != -1.0) {
                    return result * neighbor.second;
                }
            }
            return -1.0;
        };
        // Process the queries
        vector<double> results;
        for (const auto& query : queries) {
            unordered_set<string> seen;
            results.push_back(dfs(query[0], query[1], seen));
        }
        return results;
    }
};

Python

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Build the graph
        graph = {}
        for (a, b), value in zip(equations, values):
            if a not in graph:
                graph[a] = {}
            if b not in graph:
                graph[b] = {}
            graph[a][b] = value
            graph[b][a] = 1 / value

        def dfs(src: str, dst: str, visited: Set[str]) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for neighbor, value in graph[src].items():
                if neighbor in visited:
                    continue
                result = dfs(neighbor, dst, visited)
                if result != -1.0:
                    return result * value
            return -1.0

        results = []
        for query in queries:
            results.append(dfs(query[0], query[1], set()))
        return results

Java

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        
        // Build the graph
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String a = equation.get(0);
            String b = equation.get(1);
            graph.putIfAbsent(a, new HashMap<>());
            graph.putIfAbsent(b, new HashMap<>());
            graph.get(a).put(b, values[i]);
            graph.get(b).put(a, 1.0 / values[i]);
        }
        
        double[] results = new double[queries.size()];
        
        // Helper function to perform DFS
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String src = query.get(0);
            String dst = query.get(1);
            Set<String> visited = new HashSet<>();
            results[i] = dfs(graph, src, dst, visited);
        }
        
        return results;
    }
    
    private double dfs(Map<String, Map<String, Double>> graph, String src, String dst, Set<String> visited) {
        if (!graph.containsKey(src) || !graph.containsKey(dst)) {
            return -1.0;
        }
        if (src.equals(dst)) {
            return 1.0;
        }
        
        visited.add(src);
        
        Map<String, Double> neighbors = graph.get(src);
        for (Map.Entry<String, Double> neighbor : neighbors.entrySet()) {
            String nextNode = neighbor.getKey();
            if (visited.contains(nextNode)) {
                continue;
            }
            double result = dfs(graph, nextNode, dst, visited);
            if (result != -1.0) {
                return result * neighbor.getValue();
            }
        }
        
        return -1.0;
    }
}

JavaScript

var calcEquation = function (equations, values, queries) {
    const graph = {};
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        if (!graph[a]) {
            graph[a] = {};
        }
        if (!graph[b]) {
            graph[b] = {};
        }
        graph[b][a] = values[i];
        graph[a][b] = 1 / values[i];
    }

    function dfs(src, target, seen) {
        if (!graph[src] || !graph[target]) {
            return -1;
        }
        if (src === target) {
            return 1;
        }
        for (const neighbor in graph[src]) {
            if (seen.has(neighbor)) {
                continue;
            }
            const result = dfs(neighbor, target, seen.add(neighbor)) * graph[neighbor][src];
            if (result > 0) {
                return result;
            }
        }
        return -1;
    }

    return queries.map(q => dfs(q[0], q[1], new Set()));
};