LeetCode Solutions Blog

Find All Possible Recipes from Given Supplies

Number: 2220

Difficulty: Medium

Paid? No

Problem Description

Given a list of recipes with their required ingredients and an initial list of supplies, determine which recipes can be created. A recipe can be prepared if all its ingredients are available. Note that some recipes might require other recipes as ingredients.

Key Insights

Use a graph (dependency graph) where each recipe has incoming edges from its required ingredients.
Apply topological sorting: start with the initial supplies and progressively "create" recipes when all their dependencies are met.
Track in-degrees for recipes. When an ingredient (or recipe) becomes available, decrease the in-degree of all recipes that depend on it.
When a recipe’s in-degree reaches zero, it can be created and added to the result (and used as an ingredient for others).

Space and Time Complexity

Time Complexity: O(R + total_ingredients) where R is the number of recipes and total_ingredients sums up all ingredient instances. Space Complexity: O(R + I) where I is the total unique ingredients used in the dependency mapping.

Solution

We use a topological sort based on Breadth-First Search (BFS). First, we map every ingredient to the list of recipes that need it. We compute the in-degree (number of ingredients required) for each recipe. Initialize the process with the supplied ingredients. For each available ingredient, visit all recipes that depend on it, decrease their in-degree, and add any recipe with an in-degree of zero to the queue. This recipe then becomes an available ingredient for further recipes.

Code Solutions

# Python solution using BFS and topological sort.
from collections import deque, defaultdict

def findAllRecipes(recipes, ingredients, supplies):
    # Map each ingredient to the recipes that need it.
    ingredient_to_recipes = defaultdict(list)
    # Dictionary to count required number of ingredients for each recipe.
    recipe_indegree = {}
    
    # Build graph: for each recipe, iterate over its ingredients.
    for recipe, reqs in zip(recipes, ingredients):
        recipe_indegree[recipe] = len(reqs)
        for ingredient in reqs:
            ingredient_to_recipes[ingredient].append(recipe)
    
    result = []
    q = deque(supplies)  # initialize queue with initial supplies
    
    # Process available ingredients and recipes.
    while q:
        current = q.popleft()
        # If the current available item is used in any recipe, process it.
        for rec in ingredient_to_recipes[current]:
            # Decrease the recipe's requirement count.
            recipe_indegree[rec] -= 1
            # If all ingredients for the recipe are available, add recipe as an ingredient.
            if recipe_indegree[rec] == 0:
                result.append(rec)
                q.append(rec)
    
    return result

# Example usage:
recipes = ["bread", "sandwich"]
ingredients = [["yeast", "flour"], ["bread", "meat"]]
supplies = ["yeast", "flour", "meat"]
print(findAllRecipes(recipes, ingredients, supplies))  # Output: ["bread", "sandwich"]