We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All Possible Recipes from Given Supplies

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each recipe depends on its ingredients, which may include other recipes.
  • We can use a graph to represent the dependencies between recipes and their ingredients.
  • Topological sorting can be employed to determine the order of recipe creation based on available supplies.
  • A breadth-first search (BFS) approach can help in exploring which recipes can be made as supplies increase.

Space and Time Complexity

Time Complexity: O(n + e), where n is the number of recipes and e is the total number of ingredient dependencies.
Space Complexity: O(n + e), for storing the graph and the in-degree counts.

Solution

We can use a graph-based approach to solve this problem. The recipes can be treated as nodes in a directed graph where an edge from an ingredient to a recipe indicates that the recipe can be made using that ingredient. We also maintain a count of the in-degrees for each recipe, which tells us how many ingredients are still needed to make that recipe.

  1. Create a graph where each recipe is a node, and the edges point to recipes from their ingredients.
  2. Initialize an in-degree count for each recipe based on its ingredients.
  3. Use a queue to process supplies. Start with the initial supplies and add them to the queue.
  4. For each supply processed, check if it can create any recipes. If a recipe can be created (all ingredients are available), add it to the result list and update the in-degrees of other recipes.
  5. If any recipe's in-degree reaches zero, it can be added to the queue for processing.

Code Solutions

from collections import defaultdict, deque

def findAllRecipes(recipes, ingredients, supplies):
    graph = defaultdict(list)
    in_degree = {recipe: 0 for recipe in recipes}
    
    # Build the graph and in-degree count
    for i in range(len(recipes)):
        for ingredient in ingredients[i]:
            graph[ingredient].append(recipes[i])
            in_degree[recipes[i]] += 1

    # Initialize the queue with available supplies
    queue = deque(supplies)
    result = []

    while queue:
        supply = queue.popleft()

        # If the supply is a recipe, we can make it
        if supply in in_degree:
            result.append(supply)

        # Check all recipes that can be made with this supply
        for recipe in graph[supply]:
            in_degree[recipe] -= 1
            # If all ingredients are available, add to queue
            if in_degree[recipe] == 0:
                queue.append(recipe)

    return result
← Back to All Questions