658. Find All Possible Recipes from Given Supplies
You are stocking a kitchen. You get a list recipes of recipe names and a parallel list ingredients, where ingredients[i] holds every item required to cook recipes[i]. You also get supplies — items you own in unlimited quantity.
A recipe is cookable once every one of its ingredients is available, where available means the item is either in supplies or is itself a cookable recipe. Recipes may depend on other recipes, and those chains can be arbitrarily deep — but a circular dependency can never be satisfied.
Return the names of all cookable recipes, in the order they appear in recipes (that order is what the judge checks).
Example 1:
Input: recipes = ["bread"], ingredients = [["yeast", "flour"]], supplies = ["yeast", "flour", "corn"]
Output: ["bread"]
Explanation: Both of bread's ingredients (yeast and flour) are supplies, so bread is cookable. The spare corn is never needed.
Example 2:
Input: recipes = ["bread", "sandwich", "burger"], ingredients = [["yeast", "flour"], ["bread", "meat"], ["sandwich", "bread", "tomato"]], supplies = ["yeast", "flour", "meat", "tomato"]
Output: ["bread", "sandwich", "burger"]
Explanation: Bread is cookable from supplies. That unlocks sandwich (bread + meat), which in turn unlocks burger (sandwich + bread + tomato).
Constraints:
- 1 ≤ n ≤ 100, where n = recipes.length = ingredients.length
- 1 ≤ ingredients[i].length ≤ 100
- 1 ≤ supplies.length ≤ 100
- Every name is 1-10 lowercase English letters
- All recipe names are distinct, and no recipe name appears in supplies
Hints:
Cooking one recipe can unlock another that appears earlier in the list, so a single left-to-right scan is not enough. What happens if you keep re-scanning the whole list until a full pass makes no progress?
Think of it as a graph: draw an edge from each ingredient to every recipe that needs it, and store per recipe how many of its ingredients are still missing. Seed a queue with the supplies (Kahn's topological sort); whenever a recipe's missing count hits zero it becomes cookable and joins the queue as a new available item.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: recipes = ["bread"], ingredients = [["yeast", "flour"]], supplies = ["yeast", "flour", "corn"]
Expected output: ["bread"]