Problem Description

You are given information about n different recipes and need to determine which ones you can make.

Input:

• recipes: An array of strings where recipes[i] is the name of the i-th recipe
• ingredients: A 2D array where ingredients[i] contains all the ingredients needed to make recipes[i]
• supplies: An array of strings representing the ingredients you initially have (with infinite quantity of each)

Key Points:

• To create a recipe, you must have ALL its required ingredients
• A recipe can be an ingredient for another recipe (recipes can depend on other recipes)
• Once you create a recipe, it becomes available as an ingredient for other recipes
• Two recipes may contain each other in their ingredients (circular dependencies possible)

Output: Return a list of all recipes you can create. The order doesn't matter.

Example: If you have recipes = ["bread", "sandwich"], ingredients = [["flour", "water"], ["bread", "meat"]], and supplies = ["flour", "water", "meat"]:

• You can make "bread" because you have both "flour" and "water"
• Once "bread" is made, you can make "sandwich" because you now have "bread" and "meat"
• Return ["bread", "sandwich"]

The solution uses topological sorting to handle the dependency relationships between recipes. It treats the problem as a directed graph where edges point from ingredients to recipes that need them, tracking the in-degree (number of required ingredients) for each recipe. When an ingredient becomes available, it reduces the in-degree of all recipes that need it. When a recipe's in-degree reaches 0, all its ingredients are available and it can be created.

Intuition

The key insight is recognizing this as a dependency resolution problem. Each recipe depends on certain ingredients (or other recipes), and we can only make a recipe when all its dependencies are satisfied.

Think of it like a chain reaction: we start with our initial supplies, and whenever we have an ingredient available, it might "unlock" new recipes. When a recipe becomes unlocked (all its ingredients are available), it becomes a new ingredient that might unlock even more recipes.

This naturally leads us to think about graph theory. We can model this as a directed graph where:

• Each ingredient/recipe is a node
• An edge from ingredient A to recipe B means that B needs A

The problem becomes: starting from our initial supplies, which recipes can we eventually reach by following the dependency chains?

The challenge is handling the dependencies efficiently. We need to track:

1. Which recipes depend on which ingredients (the graph structure)
2. How many ingredients each recipe still needs (the "waiting count")

This is exactly what topological sorting with in-degrees does. The in-degree of a recipe represents how many ingredients it's still waiting for. When we process an available ingredient, we decrease the in-degree of all recipes that need it. When a recipe's in-degree hits 0, all its dependencies are satisfied and we can make it.

The beauty of this approach is that it handles complex dependency chains naturally. A recipe that depends on other recipes will have a higher initial in-degree, and will only become available after those prerequisite recipes are made first. The queue-based processing ensures we explore all possible recipes level by level, like a breadth-first traversal through the dependency graph.

Learn more about Graph and Topological Sort patterns.

Solution Approach

The solution implements a topological sorting algorithm using BFS (Breadth-First Search) to resolve recipe dependencies.

Data Structures Used:

1. g (graph): A dictionary mapping each ingredient to a list of recipes that need it
2. indeg (in-degree): A dictionary tracking how many ingredients each recipe needs
3. q (queue): A list that acts as a queue for BFS processing
4. ans (answer): Stores the recipes we can make

Step-by-step Implementation:

1. Build the dependency graph:

   for a, b in zip(recipes, ingredients):
       for v in b:
           g[v].append(a)
       indeg[a] += len(b)

   • For each recipe a and its ingredients list b
   • Create edges from each ingredient v to recipe a (stored in g[v])
   • Set the in-degree of recipe a to the number of ingredients it needs

2. Initialize the queue with available supplies:

   q = supplies

   • Start processing with all initially available ingredients

3. Process the queue (BFS):

   for i in q:
       for j in g[i]:
           indeg[j] -= 1
           if indeg[j] == 0:
               ans.append(j)
               q.append(j)

   • For each available ingredient i in the queue
   • Check all recipes j that need this ingredient
   • Decrease their in-degree by 1 (one dependency satisfied)
   • If in-degree reaches 0, the recipe can be made:
     • Add it to the answer list
     • Add it to the queue (it becomes a new available ingredient)

The algorithm naturally handles complex dependencies: recipes that depend on other recipes will only become available after their prerequisite recipes are made. The queue ensures we process all possibilities in the correct order, making recipes as soon as their dependencies are satisfied.

Example Walkthrough

Let's trace through a small example to see how the topological sorting approach works.

Given:

• recipes = ["cake", "frosting", "decorated_cake"]
• ingredients = [["flour", "eggs"], ["sugar", "butter"], ["cake", "frosting"]]
• supplies = ["flour", "eggs", "sugar", "butter"]

Step 1: Build the dependency graph

Create the graph g (ingredient → recipes that need it):

• "flour" → ["cake"]
• "eggs" → ["cake"]
• "sugar" → ["frosting"]
• "butter" → ["frosting"]
• "cake" → ["decorated_cake"]
• "frosting" → ["decorated_cake"]

Set up in-degrees indeg (number of ingredients each recipe needs):

• "cake": 2 (needs flour and eggs)
• "frosting": 2 (needs sugar and butter)
• "decorated_cake": 2 (needs cake and frosting)

Step 2: Initialize queue with supplies

• q = ["flour", "eggs", "sugar", "butter"]
• ans = []

Step 3: Process the queue

Process "flour":

• Check recipes needing flour: ["cake"]
• Decrease indeg["cake"] from 2 to 1
• Not zero yet, so cake can't be made

Process "eggs":

• Check recipes needing eggs: ["cake"]
• Decrease indeg["cake"] from 1 to 0
• In-degree is 0! Add "cake" to ans and q
• ans = ["cake"], q = ["flour", "eggs", "sugar", "butter", "cake"]

Process "sugar":

• Check recipes needing sugar: ["frosting"]
• Decrease indeg["frosting"] from 2 to 1
• Not zero yet

Process "butter":

• Check recipes needing butter: ["frosting"]
• Decrease indeg["frosting"] from 1 to 0
• In-degree is 0! Add "frosting" to ans and q
• ans = ["cake", "frosting"], q = [..., "cake", "frosting"]

Process "cake":

• Check recipes needing cake: ["decorated_cake"]
• Decrease indeg["decorated_cake"] from 2 to 1
• Not zero yet

Process "frosting":

• Check recipes needing frosting: ["decorated_cake"]
• Decrease indeg["decorated_cake"] from 1 to 0
• In-degree is 0! Add "decorated_cake" to ans
• ans = ["cake", "frosting", "decorated_cake"]

Final Result: ["cake", "frosting", "decorated_cake"]

The algorithm correctly identifies that we can make all three recipes, handling the dependency chain where "decorated_cake" depends on intermediate recipes "cake" and "frosting".

Solution Implementation

Time and Space Complexity

Time Complexity: O(V + E) where V is the total number of unique nodes (recipes + ingredients + supplies) and E is the total number of edges (dependencies between ingredients/supplies and recipes).

• Building the graph takes O(E) time as we iterate through all recipes and their ingredients once
• The BFS/topological sort processes each node at most once and each edge at most once, taking O(V + E) time
• Each recipe is added to the answer list at most once

Space Complexity: O(V + E)

• The graph g stores all edges, requiring O(E) space
• The indeg dictionary stores the in-degree for each recipe, using O(|recipes|) space
• The queue q can contain at most O(V) nodes in the worst case
• The ans list stores at most O(|recipes|) recipes
• Overall space is dominated by the graph structure and queue, giving us O(V + E)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Circular Dependencies Properly

A critical pitfall is assuming that circular dependencies will cause infinite loops or errors. While the problem mentions circular dependencies are possible, the topological sort approach naturally handles them - recipes involved in cycles will never have their in-degree reach 0, so they simply won't be added to the result.

Example of circular dependency:

• Recipe A needs ingredient B
• Recipe B needs ingredient A
• Neither can be made unless one is already in supplies

2. Modifying the Original Supplies List

Using supplies.copy() is crucial. If you directly use available_items = supplies and then append to it, you're modifying the original input list, which can cause issues if the caller expects the input to remain unchanged.

Incorrect approach:

available_items = supplies  # Wrong - creates reference, not copy
# Later appending to available_items modifies supplies

Correct approach:

available_items = supplies.copy()  # Creates independent copy

3. Using Wrong Data Structure for Queue Processing

The code uses a list and iterates through it while appending new items during iteration. This works in Python because the for loop internally handles the growing list, but it's not obvious behavior.

Potential confusion:

for current_item in available_items:
    # ...
    available_items.append(dependent_recipe)  # Modifying during iteration

Clearer alternative using deque:

from collections import deque
available_items = deque(supplies)
while available_items:
    current_item = available_items.popleft()
    # ... process and append new items

4. Missing Edge Case: Recipe as Its Own Ingredient

If a recipe lists itself as an ingredient (self-dependency), it can never be made unless it's already in supplies. The current approach handles this correctly by treating it like any other dependency, but developers might overlook testing this case.

5. Assuming All Recipes Must Be Makeable

The problem asks for recipes you CAN make, not all recipes. Some recipes might be impossible to make due to missing base ingredients or circular dependencies. The solution correctly returns only makeable recipes, but developers might incorrectly try to force all recipes into the result.