This problem requires identifying which recipes can be created from a set of initial supplies and other recipes used as ingredients. Using array scanning plus hash table lookups, we can efficiently track available ingredients and propagate new supplies. This ensures each recipe is only considered when all its prerequisites are met, avoiding unnecessary repeated checks.
Problem Statement
You are given a list of recipes and the corresponding ingredients needed to make each recipe. Each recipe may depend on other recipes as ingredients, and you also have a set of initial supplies with unlimited quantities. Your goal is to find every recipe that can be prepared with the available supplies and the recipes you can generate along the way.
Return a list of all recipes that can be created in any order. Each ingredient and recipe name consists of lowercase English letters, all values are unique, and each recipe's ingredient list contains no duplicates. Efficiently checking ingredient availability is key, making array scanning with hash lookups the ideal pattern for this problem.
Examples
Example 1
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
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"]
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"]
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.length
- 1 <= n <= 100
- 1 <= ingredients[i].length, supplies.length <= 100
- 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
- recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
- All the values of recipes and supplies combined are unique.
- Each ingredients[i] does not contain any duplicate values.
Solution Approach
Map Recipes to Ingredients
Build a hash table mapping each recipe to its list of ingredients. This allows O(1) checks to see which ingredients are still missing while scanning through the recipes array.
Track Available Supplies
Maintain a hash set of all initial supplies and recipes you have successfully created. Iteratively scan the recipes array and add recipes to the set once all their ingredients are available, ensuring no recipe is processed before its prerequisites.
Iteratively Expand Possibilities
Repeat scanning until no new recipes can be added. This ensures all dependent recipes are considered in topological order without building an explicit graph. Return all recipes successfully added to the available set.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n + m + s) |
| Space | O(n + m + s) |
Time complexity is O(n + m + s), where n is the number of recipes, m is the total number of ingredient entries, and s is the number of initial supplies. Space complexity is O(n + m + s) for the hash tables storing recipes, ingredients, and available supplies.
What Interviewers Usually Probe
- Can you efficiently track which ingredients are available without repeatedly scanning all recipes?
- What data structure helps quickly determine if a needed ingredient exists in your current supplies?
- How would you handle a recipe that depends on another recipe not yet created?
Common Pitfalls or Variants
Common pitfalls
- Failing to account for recipes that depend on other recipes as ingredients, causing incorrect availability checks.
- Re-scanning all recipes without updating the available ingredients set, leading to unnecessary repeated work.
- Not using a hash set for supplies, resulting in O(n*m) lookups instead of O(1) checks per ingredient.
Follow-up variants
- Count the number of possible recipes you can make rather than returning the list.
- Given a target recipe, determine the minimal set of supplies needed to create it.
- Handle recipes with circular dependencies and return only recipes that are safe to create.
How GhostInterview Helps
- Identifies the optimal hash table and array scanning approach to manage ingredient availability efficiently.
- Guides iterative scanning and recipe expansion while preventing repeated unnecessary checks.
- Highlights dependency patterns between recipes to ensure all possible creations are discovered systematically.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What pattern does 'Find All Possible Recipes from Given Supplies' use?
It uses array scanning combined with hash table lookups to efficiently track available ingredients and propagate newly creatable recipes.
Can the recipes be returned in any order?
Yes, the problem allows the output list to be in any order as long as all creatable recipes are included.
How do I handle a recipe that requires another recipe as an ingredient?
Treat each successfully created recipe as a new supply and iteratively check dependent recipes until no new recipes can be added.
What data structures are most effective for this problem?
A hash set for available supplies and a hash map for recipe to ingredient mapping ensures constant-time lookups and efficient scanning.
What is the main failure mode in this problem?
The main failure is prematurely checking recipes before all their dependent ingredients are available, which can lead to missing valid recipes.
Need direct help with Find All Possible Recipes from Given Supplies instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find All Possible Recipes from Given Supplies from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the longest path in a tree where adjacent nodes have different characters using graph DFS and topological reasoning.
Open problem page#2131 Longest Palindrome by Concatenating Two Letter WordsFind the maximum-length palindrome by combining two-letter words using array scanning and hash table lookups efficiently.
Open problem page#2135 Count Words Obtained After Adding a LetterGiven startWords and targetWords, check how many targetWords can be formed by adding one letter and rearranging letters of startWords.
Open problem page