Coding Week 12 - Graphs

Question 1

Problem 1) Find All Possible Recipes from Given Supplies

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.
You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.

Example 1:
Input: recipes = [“bread”], ingredients = [[“yeast”,”flour”]], supplies = [“yeast”,”flour”,”corn”]
Output: [“bread”]

Explanation:
We can create “bread” since we have the ingredients “yeast” and “flour”.

Question 1) Which type of graph problem is it?

A) Shortest Path Finding Problem
B) Hamiltonian Path Problem
C) Cycle Detection
D) Route Inspection

Answer 1

C) Cycle Detection

This is a graph traversal problem with cycle detection (since two recipes can contain each other). We construct a graph containing edges from recipes to their ingredients. Then we do graph traversal from all the recipe nodes. When we visit a node in the graph we add it to a set making which means that we are in the process of making this recipe or ingredient. If while visiting a node we find that we are already making it, it means we have run into a cycle and this recipe cannot be made. Also if an ingredient is neither a recipe nor a supply there is no need to visit this node as it cannot be part of the solution. While visiting a node we visit all the edges attached to that node. Once we have visited all the edges we add it to the set to avoid repeated traversals. Note that this set will also contain ingredients since they are nodes of the graph. Visiting a node successfully means we can “make” that recipe or ingredient. Since the final answer requires only recipes we add only successfully visited recipe nodes to the final answer.

Question 2

Problem 1) Find All Possible Recipes from Given Supplies

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.
You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.

Example 1:
Input: recipes = [“bread”], ingredients = [[“yeast”,”flour”]], supplies = [“yeast”,”flour”,”corn”]
Output: [“bread”]

Explanation:
We can create “bread” since we have the ingredients “yeast” and “flour”.

Question 2) What is the minimum time and auxiliary space possible to solve this problem?

A) Time - O(V + E), Space - O(V)
B) Time - O(V), Space - O(V)
C) Time - O(E), Space - O(V)
D) Time - O(V * E), Space - O(1)

Answer 2

A) Time - O(V + E), Space - O(V)

Explanation: We use be performing topological sort to solve this problem.
The time complexity of topological sort is O(V+E), where V = Vertices, E = Edges.
To find out the time complexity of the algorithm, let’s try to find the time complexity of each of the steps:
To determine the in-degree of each node, we will have to iterate through all the edges of the graph. So the time complexity of this step is O(E).

Next, look for nodes with in-degrees equal to 0. This will require us to iterate through the entire array that stores the in-degrees of each node. The size of this array is equal to V. So, the time complexity of this step is O(V).
For each node with an in-degree equal to zero, we remove it from the graph and decrement the in-degrees of the nodes it connected to. In the entire run of the algorithm, the number of times we have to perform the decrement operation is equal to the number of edges. So it will take O(E) time.
Whenever we decrement the in-degree of a node, we check if the node has achieved in-degree = 0 status. When this happens, we move it to the stack. In the entire run of the algorithm, it can occur at max (V-1) times. So the run time of this operation is O(V).
In the end, we compare the size of the resultant topologically sorted array and the size of the graph to ensure that it was not a cyclic graph. This operation is done in O(1) time.

So, adding all the individual run times, the time complexity of topological sort is O(V+E).
This is the best case, worst case, and average-case time complexity of this algorithm since we perform the same steps regardless of how the elements are organized.
Topological Sort Space Complexity
Auxiliary space required is O(V).
We have to create one array to store the in-degrees of all the nodes. This will require O(V) space.

We have to store the nodes with in-degree = 0 in a data structure (stack or queue) when we remove them from the graph. In the worst case, the data structure will store all the graph nodes, requiring O(V)space.
Finally, we need an array to store all the nodes in sorted order. This will naturally require O(V) space.
Adding all three, we arrive at the space complexity of O(V).