Find All Possible Recipes from Given Supplies

Explanation & Solution

Description

You have information about n recipes. You are given a string array recipes and a 2D string array ingredients, where ingredients[i] is a list of items needed to create recipes[i]. You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of each.

Return a list of all the recipes that you can create. A recipe can be an ingredient of another recipe, meaning you may use the output of one recipe as an ingredient for another.

You may return the answer in any order.

Input:recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]

bread

yeast

flour

corn

Output:["bread"]

bread

Explanation: We have all the ingredients needed for "bread", so we can create it.

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 values of recipes and supplies combined are unique
Each ingredients[i] does not contain any duplicate values

Approach

Topological Sort pattern

1. Initialize Available Supplies

Place all initial supplies into a Set for O(1) lookup.
Create a set of recipe names to distinguish recipes from raw supplies.

2. Build the Dependency Graph

For each recipe, iterate through its ingredients.
If an ingredient is already in our supplies, it costs nothing — skip it.
If an ingredient is NOT a supply, it must be another recipe. Create a directed edge from that ingredient to the current recipe and increment the recipe's in-degree.

3. Initialize the BFS Queue

Any recipe with in-degree 0 can be made immediately (all its ingredients are available supplies).
Add all such recipes to the queue.

4. Process with Topological Sort (BFS)

Dequeue a recipe, add it to the result.
For each recipe that depends on the current one, decrement its in-degree.
If a dependent recipe's in-degree reaches 0, all its ingredients are now available — add it to the queue.

5. Return the Result

The result list contains all recipes that can be created in a valid order.
Recipes involved in circular dependencies will never reach in-degree 0, so they are automatically excluded.

Key Insight

This is a classic topological sort on a dependency graph. Recipes are nodes, and edges represent "recipe A is needed to make recipe B". By processing recipes in topological order, we ensure dependencies are resolved before dependents.

Time

O(n * m) where n is the number of recipes and m is the average number of ingredients.

Space

O(n * m) for the graph and in-degree map.

Solution Code

Verifying an Alien Dictionary

Parallel Courses