How do you solve Find All Possible Recipes from Given Supplies on LeetCode?

Find All Possible Recipes from Given Supplies (LeetCode #2115) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + m) time complexity and O(n + m) space complexity. Key insight: Understanding dependencies between recipes and ingredients is crucial.

What is the brute force solution for Find All Possible Recipes from Given Supplies?

The brute force approach for Find All Possible Recipes from Given Supplies is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we check each recipe and see if we can create it using the supplies we have. This involves checking all ingredients for each recipe against the supplies, which can be inefficient. The optimal Optimal Solution approach improves this to O(n + m).

What algorithm or data structure is used to solve Find All Possible Recipes from Given Supplies?

Find All Possible Recipes from Given Supplies uses the following concepts: Array, Hash Table, String, Graph Theory, Topological Sort. The recommended patterns to study are: Hash Map, Graph Traversal.

What are the interview tips for Find All Possible Recipes from Given Supplies?

Clarify the problem requirements and constraints before jumping to code. Think about edge cases, such as no recipes or all supplies available. Explain your thought process as you code; it helps interviewers understand your reasoning.

What are common mistakes when solving Find All Possible Recipes from Given Supplies?

Not considering recipes that can be made from other recipes. Failing to use a set for quick lookups of supplies.

#2115

Find All Possible Recipes from Given Supplies

Medium

ArrayHash TableStringGraph TheoryTopological SortHash MapGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + m)
Space	O(1)	O(n + m)

💡

Intuition

Time O(n + m)Space O(n + m)

The optimal approach uses a graph-like structure to track dependencies between recipes and ingredients. We can use a queue to process recipes that can be created once their ingredients are available, allowing us to efficiently determine all possible recipes.

⚙️

Algorithm

3 steps

1Step 1: Create a mapping of recipes to their ingredients and a count of how many ingredients each recipe needs.
2Step 2: Use a set to keep track of available supplies and initialize a queue with the supplies.
3Step 3: While the queue is not empty, check if any recipes can be created with the current supplies, adding them to the available supplies and the result list.

solution.py21 lines

1from collections import defaultdict, deque
2
3def findAllRecipes(recipes, ingredients, supplies):
4    supply_set = set(supplies)
5    recipe_map = defaultdict(list)
6    indegree = defaultdict(int)
7    for i, recipe in enumerate(recipes):
8        indegree[recipe] = len(ingredients[i])
9        for ingredient in ingredients[i]:
10            recipe_map[ingredient].append(recipe)
11    queue = deque(supplies)
12    result = []
13    while queue:
14        current_supply = queue.popleft()
15        if current_supply in recipe_map:
16            for recipe in recipe_map[current_supply]:
17                indegree[recipe] -= 1
18                if indegree[recipe] == 0:
19                    result.append(recipe)
20                    queue.append(recipe)
21    return result

ℹ

Complexity note: This complexity is due to processing each recipe and ingredient once, where n is the number of recipes and m is the total number of ingredients across all recipes.

1Understanding dependencies between recipes and ingredients is crucial.
2Using a graph-like approach can simplify the problem of tracking which recipes can be created.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.