⚡Flashcard Drill➔
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

  1. Model recipes as nodes and ingredients as prerequisites: a recipe's in-degree is the number of its missing ingredients.
  2. Ingredients already in supplies impose no in-degree.
  3. Kahn's algorithm: start with recipes whose in-degree is 0, and each made recipe decrements the in-degree of recipes needing it.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems