Find All Possible Recipes from Given Supplies

01 · Question

Given recipes and their ingredient lists, and initial supplies, return all recipes you can make. A recipe becomes available when all its ingredients are available.

02 · Analysis

Count every distinct ingredient, including ingredients that are themselves recipes. Build ingredient -> waiting recipes, then publish initially supplied items and recipes requiring nothing. Each item becomes available once. Decrement a waiting count only when that ingredient is published; reaching zero unlocks the recipe. Missing ingredients and cycles without an available starting item never unlock. With R recipes, I ingredient entries and S supplies, time and space are O(R+I+S) under expected constant-time hashing.

03 · Solution

Reference solution

1from collections import deque
2
3def findAllRecipes(recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
4    waiting = {}
5    remaining = {}
6    for recipe, required in zip(recipes, ingredients):
7        unique = set(required)
8        remaining[recipe] = len(unique)
9        for item in unique:
10            waiting.setdefault(item, []).append(recipe)
11    available = set(supplies)
12    available.update(recipe for recipe in recipes if remaining[recipe] == 0)
13    queue = deque(available)
14    while queue:
15        item = queue.popleft()
16        for recipe in waiting.get(item, []):
17            remaining[recipe] -= 1
18            if remaining[recipe] == 0 and recipe not in available:
19                available.add(recipe)
20                queue.append(recipe)
21    return [recipe for recipe in recipes if recipe in available]

Course Schedule II

Count Paths in a DAG