Find All Possible Recipes from Given Supplies

Medium#2115

You get a list of recipes, the ingredients of each recipe and the supplies you have plenty of. An ingredient is either a supply or another recipe, which has to be made first; anything else cannot be had. Return every recipe that can be made, in any order. Our example: dough from flour, water; pasta from dough, eggs; crepe from flour, eggs, milk; cake from crepe, sugar. The supplies: flour, water, eggs, sugar. The answer is dough and pasta.

2115 Find All Possible Recipes from Given SuppliesWalkthrough · 1×

Example: Supplies on the left, recipes to the right, an arrow from each ingredient to the recipe that needs it. The number above a recipe is how many of its ingredients are still missing.

flourwatereggsmilksugardoughcrepepastacakequeuefront on the left—made—
waits for ingredientsin the queue: we have itcurrent itemthe recipe the arrow leads tomadecan never be had

Draw an arrow from each ingredient to every recipe that needs it

01/37
restart · back · play · step
Speed
1function findAllRecipes(recipes, ingredients, supplies):
2 neededBy = the recipes that need each ingredient
3 missing = number of ingredients of each recipe
4 queue = supplies
5 made = []
6 while queue is not empty:
7 item = queue.popFront()
8 for recipe in neededBy[item]:
9 decrease missing[recipe] by 1
10 if missing[recipe] is 0:
11 made.pushBack(recipe)
12 queue.pushBack(recipe)
13 return made
state
missing
–
queue
–
made
–
item
–
recipe
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A recipe reaches 0 missing only after each of its ingredients has come out of the queue, and only supplies and made recipes ever go into it.
  2. A made recipe goes into the queue like a supply, so a recipe that needs it, such as pasta after dough, gets its turn.
  3. An ingredient that is neither a supply nor a makeable recipe never comes out of the queue, so a recipe that needs it, and every recipe after it, keeps a count above 0. A loop of recipes stays above 0 the same way.

Complexity

Time O(r + i + s) for r recipes, i ingredients in all the lists and s supplies: each list entry becomes one arrow and is followed once, and each item enters the queue at most once. Memory O(r + i + s) for the arrows, the counts and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.