NeetCode #599LC-2115MediumGraphs
← Back to All Problems#599 · #2115 · Find All Possible Recipes from Given Supplies(从给定原材料中找到所有可以做出的菜)
📌 Problem Statement & Constraints
You are given
recipes, ingredients (parallel arrays) and supplies (initially available items). A recipe can be made when all its ingredients are available; a made recipe becomes an available ingredient. Return all recipes that can be made, in any order. Constraints: 1 <= recipes.length <= 100, 1 <= ingredients[i].length <= 100.💡 Core Algorithmic Approaches
- Model recipes as nodes and ingredients as prerequisites: a recipe's in-degree is the number of its missing ingredients.
- Ingredients already in
suppliesimpose no in-degree. - Kahn's algorithm: start with recipes whose in-degree is 0, and each made recipe decrements the in-degree of recipes needing it.
- This is exactly topological sort over the recipe dependency graph.
💻 Benchmark Python3 Implementation
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
from collections import defaultdict, deque
have = set(supplies)
g = defaultdict(list) # ingredient -> recipes needing it
indeg = {}
for r, ings in zip(recipes, ingredients):
need = 0
for ing in ings:
if ing not in have: # only missing ingredients count
g[ing].append(r)
need += 1
indeg[r] = need
q = deque(r for r in recipes if indeg[r] == 0)
res = []
while q:
r = q.popleft()
res.append(r) # this recipe is now makeable
for nxt in g[r]: # r is now available as an ingredient
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total ingredients + recipes): each dependency edge is processed once.
💾 Space Complexity
O(total ingredients) for the graph.
⚠️ Interview Pitfalls & Follow-ups
- Counting all ingredients in the in-degree: only the missing ones count.
- Assuming the initial supplies are enough: recipes may depend on each other.
- Re-scanning the recipe list repeatedly: O(R^2 * I) instead of one topological pass.
- Forgetting that a made recipe becomes an ingredient: that is what the decrement models.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.