< Back




399. Evaluate Division

Super tricky question - really only solvable if you realize this is supposed to be a graph / DFS
problem. We're given a list of equations, these just being a list of pairs of characters - each
character should be treated as a node and each pairing should be treated as an edge. We're given a
list of values correlating to each edge, this is the quotient for the two nodes during division.
This should be considered the weight of each edge. Finally, we're given a list of queries, two nodes
and we're asked to return an answer list that resolves the quotient for each query.

Treating each pairs as an edge, we reconstruct the graph with weighted edges. For a particular
dictionary spot in the graph, referencing a node, we'll have another dictionary mapping the
denominator and the value of the edge (quotient). For each query, we conduct a DFS with the start
and end nodes, multiplying the quotients of each edge as we go. If we reach the end node, we return
the product of the quotients. If we don't, we return -1.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def calcEquation(
          self, equations: List[List[str]], values: List[float], queries: List[List[str]]
      ) -> List[float]:
          def answer_query(start, end):
              if start not in graph:
                  return -1

              seen = {start}
              stack = [(start, 1)]

              while stack:
                  node, ratio = stack.pop()
                  if node == end:
                      return ratio

                  for neighbor in graph[node]:
                      if neighbor not in seen:
                          seen.add(neighbor)
                          stack.append((neighbor, ratio * graph[node][neighbor]))

              return -1

          graph = defaultdict(dict)
          for i in range(len(equations)):
              numerator, denominator = equations[i]
              val = values[i]
              graph[numerator][denominator] = val
              graph[denominator][numerator] = 1 / val

          ans = []
          for numerator, denominator in queries:
              ans.append(answer_query(numerator, denominator))

          return ans


_ Time Complexity:

  O(n * m) - Where n is the number of equations and m is the number of queries.

_ Space Complexity:

  O(n) - Where n is the number of equations.