Find All Possible Recipes from Given Supplies - Solution & Explanation
Problem Statement
You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.
You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Example 1:
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"] Output: ["bread"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour".
Example 2:
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
Example 3:
Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich","burger"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread". We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".
Constraints:
n == recipes.length == ingredients.length1 <= n <= 1001 <= ingredients[i].length, supplies.length <= 1001 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10recipes[i], ingredients[i][j], andsupplies[k]consist only of lowercase English letters.- All the values of
recipesandsuppliescombined are unique. - Each
ingredients[i]does not contain any duplicate values.
Approach 1: Topological Sort using Kahn's Algorithm
This approach uses graph theory to solve the problem. Each recipe and ingredient is considered a node. An edge from node A to node B indicates that node B is needed to create node A. We can then perform a topological sort utilizing Kahn's Algorithm to determine the order in which we can create the recipes.
In this implementation, we first build the graph and compute the in-degrees of each recipe. We fill the queue with our initial supplies and perform a BFS. We decrement the in-degree of the neighboring nodes when visiting each node, and if a neighbor's in-degree becomes zero, it means that all ingredients to make it are available, so we add it to the queue.
Complexity
Time Complexity: O(n + m), where n is the number of recipes and m is the total number of ingredients.
Space Complexity: O(n + m), due to the graph and in-degree storage.
Approach 2: Backtracking with Memoization
This approach involves trying to create each recipe by checking if all its ingredients are available or can be created from other recipes. We use memoization to store the results of subproblems, avoiding redundant calculations.
This implementation checks each recipe to see if it can be created using a recursive backtracking approach. It covers all subproblems using memoization, thereby improving efficiency. An ingredient is considered ready if it can be created from available supplies, its own recipe, or if it already appears in supplies.
Complexity
Time Complexity: O(n * m), where n is the number of recipes and m is the average number of ingredients.
Space Complexity: O(n + m), due to the auxiliary data structures used for memoization and recursion stack.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Topological Sort using Kahn's Algorithm | Time Complexity: O(n + m), where n is the number of recipes and m is the total number of ingredients. |
| Backtracking with Memoization | Time Complexity: O(n * m), where n is the number of recipes and m is the average number of ingredients. |
| Default Approach | — |
Video Solution
Find All Possible Recipes from Given Supplies - Leetcode 2115 - Python • NeetCodeIO • 12,565 views views
Watch 9 more video solutions →Ready to solve this problem?
Practice Find All Possible Recipes from Given Supplies with our built-in code editor and test cases.
Practice on FleetCode