{x}
blog image

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]. A recipe can also be an ingredient for 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".

Example 2:

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Example 3:

Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

 

Constraints:

  • n == recipes.length == ingredients.length
  • 1 <= n <= 100
  • 1 <= ingredients[i].length, supplies.length <= 100
  • 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
  • recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
  • All the values of recipes and supplies combined are unique.
  • Each ingredients[i] does not contain any duplicate values.

Solution Explanation

This problem can be efficiently solved using a topological sort algorithm. The recipes and their ingredients form a directed acyclic graph (DAG), where recipes are nodes, and ingredients are edges. We aim to find all recipes that can be made given the initial supplies.

Algorithm:

  1. Build the graph: Create an adjacency list (g) to represent the recipe dependencies. Each ingredient points to the recipes it's used in. Also, create an indegree map to track the number of ingredients needed for each recipe.

  2. Initialize the queue: Start with a queue (q) containing the initial supplies.

  3. Topological Sort: Iteratively process the queue. For each item in the queue:

    • Decrement the indegree of all recipes that depend on that item.
    • If the indegree of a recipe becomes 0, it means all its ingredients are available, so add the recipe to the queue and the result list (ans).

  4. Return the result: The ans list contains all the recipes that can be made.

Time Complexity Analysis:

  • Building the graph takes O(R*I) time, where R is the number of recipes, and I is the maximum number of ingredients per recipe.
  • The topological sort takes O(R + I) time in the best case (if all recipes can be made) and O(R*I) in the worst case (if many recipes have complex dependencies and many are not possible).
  • Overall, the time complexity is dominated by the graph building and the topological sort, resulting in a worst-case time complexity of O(R*I).

Space Complexity Analysis:

  • The space complexity is O(R + I) to store the graph, indegree map, and queue. The output list ans can have at most R elements.
  • Therefore, the overall space complexity is O(R + I).

Code Explanation (Python):

from collections import defaultdict
 
class Solution:
    def findAllRecipes(
        self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]
    ) -> List[str]:
        g = defaultdict(list)  # Adjacency list: ingredient -> recipes
        indeg = defaultdict(int)  # Indegree: recipe -> count of needed ingredients
        for recipe, ings in zip(recipes, ingredients):
            for ing in ings:
                g[ing].append(recipe)
            indeg[recipe] = len(ings)  # Initialize indegree
 
        q = supplies[:] #Create a copy of supplies to avoid modification
        ans = []
        while q:
            next_q = []
            for item in q:
                for recipe in g[item]:
                    indeg[recipe] -= 1
                    if indeg[recipe] == 0:
                        ans.append(recipe)
                        next_q.append(recipe)
            q = next_q #Update queue with newly created recipes
 
        return ans

The other language solutions (Java, C++, Go) follow the same logic with minor syntactic variations. They all use efficient data structures (hash maps and queues) to achieve the optimal time and space complexity.