Find All Possible Recipes from Given Supplies

main.md

Question

Approach

I use a topological sorting (Kahn's algorithm) approach with a graph-based representation.

1. Construct a directed graph where each ingredient points to the recipes that depend on it.
2. Maintain an in-degree counter to track how many ingredients are needed for each recipe.
3. Use a queue to process supplies and propagate the ability to cook recipes.
4. If a recipe's in-degree reaches zero, it can be made and is added to the queue.
5. The process continues until no more recipes can be created.

Implementation

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        available = set(supplies)
        graph = defaultdict(list)
        in_degree = {}
        
        for i, recipe in enumerate(recipes):
            in_degree[recipe] = len(ingredients[i])
            for ing in ingredients[i]:
                graph[ing].append(recipe)
        
        queue = deque(supplies)
        result = []
        
        while queue:
            ing = queue.popleft()
            if ing in in_degree and in_degree[ing] == 0:
                result.append(ing)
            
            for recipe in graph[ing]:
                in_degree[recipe] -= 1
                if in_degree[recipe] == 0:
                    queue.append(recipe)
        
        return result

Complexities

• Time: O(n + m), where n is the number of recipes and m is the total number of ingredient-recipe dependencies.
• Space: O(n + m) for storing the graph and in-degree counts.