algoadvance

Leetcode 399. Evaluate Division

Problem Statement:

You are given equations in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point). 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]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are:
a / c = ? , b / a = ? , a / e = ? , a / a = ? , x / x = ? 
results: 6.0, 0.5, -1.0, 1.0, -1.0

Clarifying Questions:

  1. Are the variables in the equations guaranteed to be lower case letters?
  2. Can the length of equations and queries be very large?
  3. Is there any specific precision requirement for the results?

Strategy:

  1. Graph Representation:
    • Model the problem as a graph. Each variable is a node, and a directed edge (A -> B) represents the division relationship (A / B = k).
  2. Graph Construction:
    • Construct the graph using given equations and values. For each equation A / B = k, add edges A -> B with weight k and B -> A with weight 1/k.
  3. Query Evaluation using DFS:
    • For each query A / B, use Depth-First Search (DFS) to find a path from A to B and keep track of the product of edge weights along the path.
  4. Edge Cases:
    • A node divided by itself returns 1.0.
    • If either variable in the query doesn’t exist in the graph, return -1.0.
    • Handle cases where there is no path between the two variables in the query.

Code:

import java.util.*;

public class EvaluateDivision {
    
    class Node {
        String dest;
        double value;
        Node(String dest, double value) {
            this.dest = dest;
            this.value = value;
        }
    }
    
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, List<Node>> graph = new HashMap<>();

        // Build the graph
        for (int i = 0; i < equations.size(); i++) {
            String u = equations.get(i).get(0);
            String v = equations.get(i).get(1);
            double value = values[i];

            graph.putIfAbsent(u, new ArrayList<>());
            graph.putIfAbsent(v, new ArrayList<>());

            graph.get(u).add(new Node(v, value));
            graph.get(v).add(new Node(u, 1.0 / value));
        }

        double[] results = new double[queries.size()];

        for (int i = 0; i < queries.size(); i++) {
            String u = queries.get(i).get(0);
            String v = queries.get(i).get(1);

            if (!graph.containsKey(u) || !graph.containsKey(v)) {
                results[i] = -1.0;
            } else if (u.equals(v)) {
                results[i] = 1.0;
            } else {
                Set<String> visited = new HashSet<>();
                results[i] = dfs(graph, u, v, 1.0, visited);
            }
        }

        return results;
    }

    private double dfs(Map<String, List<Node>> graph, String src, String dest, double product, Set<String> visited) {
        if (src.equals(dest)) {
            return product;
        }
        
        visited.add(src);

        for (Node neighbor : graph.get(src)) {
            if (!visited.contains(neighbor.dest)) {
                double result = dfs(graph, neighbor.dest, dest, product * neighbor.value, visited);
                if (result != -1.0) {
                    return result;
                }
            }
        }

        return -1.0;
    }

    public static void main(String[] args) {
        EvaluateDivision solver = new EvaluateDivision();

        List<List<String>> equations = Arrays.asList(
            Arrays.asList("a", "b"),
            Arrays.asList("b", "c")
        );
        double[] values = {2.0, 3.0};
        List<List<String>> queries = Arrays.asList(
            Arrays.asList("a", "c"),
            Arrays.asList("b", "a"),
            Arrays.asList("a", "e"),
            Arrays.asList("a", "a"),
            Arrays.asList("x", "x")
        );

        double[] result = solver.calcEquation(equations, values, queries);
        System.out.println(Arrays.toString(result));  // Output: [6.0, 0.5, -1.0, 1.0, -1.0]
    }
}

Time Complexity:

  1. Graph Construction: O(E), where E is the number of edges or equations.
  2. DFS Traversal: In the worst case, each query may traverse all nodes, leading to O(V + E) per query. Assuming E = O(V) due to the nature of the equation relationships, the complexity per query is O(V).

Hence, for Q queries, the overall time complexity is O(Q * (V + E)).

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