CODEWITHSUNDEEP
javaalgorithmdata-structuresgraphtree
AlgorithmCoder
AlgorithmCoder

Reputation: 21

Path sum in a Directed Acyclic Graph

Given a directed acyclic graph, determine if any branch returns a path sum that equals 22. In the example below, such a path can be found at (7 + 8 + 3 + 4). What is the run time complexity of such an algorithm?

      7  
     / \  
    8   6  
   / \ / \  
  2   3   8  
 /   /    \     
5   4      1

This is what I came up with. 

public boolean hasPathToSum(Node root, int sum)
{
    if (root == null) return false;
    if (root.value == sum && (root.left == null && root.right == null))
        return true;

    return hasPathToSum(root.left, sum - root.value) || hasPathToSum(root.right, sum - root.value);
}

Any better suggestions on improving the complexity?

Upvotes: 2

Views: 1035

Answers (1)

Ivan Smirnov
Ivan Smirnov

Reputation: 4435

If all values in the graph are nonnegative you can solve this problem in O((n + m) * sum) using memoization. In your case sum is fixed and equal to 22, so the solution is effectively linear.

Memoization is a technique not to compute the same value twice. Note that hasPathToSum(root, sum) is a pure function: its result depends only on arguments, it has no side effects. It means that we can save the result of this function into some map (root, sum) -> bool (probably a HashMap or a TreeMap in Java, I cannot say precisely as I'm not familiar with the language).

Now, when calling the function, we check if its arguments are presented in the map. If yes, just return saved value. Otherwise calculate it, save into the map and return. This way the function will be really computed only once for any set of arguments.

The last optimization works only with nonnegative values. Note that the result of hasPathToSum(v, x) is false if x < 0. So you can make a cutoff: just return false immediately if this is the case. This optimization ensures that, for each node, hasPathToSum will be called with at most 23 different sum values, yielding the aforementioned running time.

Upvotes: 2

Related Questions