Find All Possible Recipes from Given Supplies
MedPrompt
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]. A recipe can also be an ingredient for 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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process of cooking recipes iteratively. We start with the initial supplies and in each round, we try to create new recipes with the ingredients we currently have. We repeat this process until no new recipes can be created in a full round.
Algorithm
- Initialize a
Setof available items with the initialsuppliesfor efficient lookup. - Create a list to store the final creatable recipes.
- Use a
booleanarray to track which recipes have already been created. - Enter a loop that continues as long as new recipes are being made.
- Inside the loop, iterate through all recipes. For each uncreated recipe, check if all its ingredients are in the
availableset. - If all ingredients are available, the recipe can be created. Add it to the result list, the
availableset, and mark it as created. - If a full pass over all recipes results in no new creations, the loop terminates.
- Return the list of created recipes.
Walkthrough
The core idea is to repeatedly scan all the recipes. We maintain a set of all ingredients we possess, which initially contains just the supplies. We then loop through the recipes. If we find a recipe for which we have all the ingredients, we 'create' it. This means we add the recipe itself to our set of available items and to our final answer list. We continue this process, looping over the recipes again and again, because creating one recipe might enable us to create another. The process stops when we complete a full pass through all recipes without being able to create any new ones, indicating that we can't make any further progress.
import java.util.*; class Solution { public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) { Set<String> available = new HashSet<>(Arrays.asList(supplies)); List<String> result = new ArrayList<>(); int n = recipes.length; boolean[] created = new boolean[n]; boolean newRecipeMadeInRound = true; // Keep iterating as long as we are creating new recipes while (newRecipeMadeInRound) { newRecipeMadeInRound = false; for (int i = 0; i < n; i++) { // Skip recipes that have already been created if (created[i]) { continue; } boolean canCreate = true; // Check if all ingredients for the current recipe are available for (String ingredient : ingredients.get(i)) { if (!available.contains(ingredient)) { canCreate = false; break; } } // If all ingredients are available, create the recipe if (canCreate) { result.add(recipes[i]); available.add(recipes[i]); created[i] = true; newRecipeMadeInRound = true; } } } return result; }}Complexity
Time
O(N^2 * M * K), where N is the number of recipes, M is the maximum number of ingredients for a recipe, and K is the maximum length of a string. The outer `while` loop can run at most N times (as we create at least one recipe per successful iteration). Inside, we loop through N recipes. For each recipe, we check up to M ingredients. Set lookups take O(K) on average for hashing the string.
Space
O((S + N) * K), where S is the number of supplies, N is the number of recipes, and K is the maximum string length. This is for storing the `available` set, which can hold up to S initial supplies and N created recipes. The result list also contributes O(N * K) space.
Trade-offs
Pros
Simple to understand and implement.
Doesn't require knowledge of complex data structures or algorithms like graphs.
Cons
Inefficient due to repeated scanning of all recipes.
The time complexity is polynomial, which might be too slow for larger constraints.
This problem can be modeled as a dependency graph, where recipes are nodes and an ingredient requirement forms a directed edge. If recipe R needs ingredient I, there's an edge from I to R. Finding all creatable recipes is equivalent to performing a topological sort on this graph, starting from the initial supplies.
Algorithm
- Model the problem as a graph. Create an adjacency list
adjmapping each ingredient to the list of recipes that require it. - Create an
inDegreemap to store the number of ingredients required for each recipe. - Initialize a queue with all the initial
supplies. These are the starting points of our topological sort, as they have no prerequisites. - Create a
Setof all recipe names for quick lookups. - Process the queue: while it's not empty, dequeue an item.
- If the dequeued item is a recipe, add it to the result list.
- For the dequeued item, find all recipes that depend on it using the
adjmap. - For each such dependent recipe, decrement its in-degree. If a recipe's in-degree becomes 0, it means all its ingredients are now available, so add it to the queue.
- After the queue is empty, the result list contains all recipes that could be created in a valid order.
Walkthrough
A more efficient way to solve this problem is to recognize it as a dependency problem, which is a classic use case for topological sorting. We can think of recipes and ingredients as nodes in a directed graph. An edge from an ingredient I to a recipe R signifies that R depends on I.
A recipe can be created only when all its prerequisite ingredients are available. In graph terms, a node can be 'visited' (or a recipe created) only after all its preceding nodes have been visited. This is the exact principle of topological sorting.
We use Kahn's algorithm for topological sorting. We start by building the graph representation: an adjacency list to show which recipes depend on which ingredients, and an in-degree count for each recipe to track how many ingredients are still needed. We initialize a queue with all the initial supplies, as they are the items we have from the start (in-degree 0, conceptually). Then, we process items from the queue. When we process an item (supply or a newly created recipe), we find all recipes that depend on it and reduce their in-degree. If a recipe's in-degree drops to zero, it means all its ingredients are now available, and we can add it to the queue to be processed. Recipes that are part of a cycle (e.g., A needs B, B needs A) will never have their in-degrees drop to zero, so they are correctly excluded.
import java.util.*; class Solution { public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) { // Adjacency list: ingredient -> list of recipes that need it Map<String, List<String>> adj = new HashMap<>(); // In-degree map: recipe -> number of ingredients needed Map<String, Integer> inDegree = new HashMap<>(); // Set of all recipes for quick O(1) average time lookups Set<String> recipeSet = new HashSet<>(Arrays.asList(recipes)); // Build the graph for (int i = 0; i < recipes.length; i++) { String recipe = recipes[i]; inDegree.put(recipe, ingredients.get(i).size()); for (String ingredient : ingredients.get(i)) { adj.computeIfAbsent(ingredient, k -> new ArrayList<>()).add(recipe); } } // Queue for topological sort, initialized with available supplies Queue<String> queue = new LinkedList<>(); for (String supply : supplies) { queue.offer(supply); } List<String> result = new ArrayList<>(); while (!queue.isEmpty()) { String item = queue.poll(); // If this item is a recipe that can be made, add to result // We only add recipes to the result, not basic supplies if (recipeSet.contains(item)) { result.add(item); } // If this item is an ingredient for other recipes, update their in-degrees if (adj.containsKey(item)) { for (String dependentRecipe : adj.get(item)) { inDegree.put(dependentRecipe, inDegree.get(dependentRecipe) - 1); // If a recipe's in-degree becomes 0, it can now be made if (inDegree.get(dependentRecipe) == 0) { queue.offer(dependentRecipe); } } } } return result; }}Complexity
Time
O((L + S) * K), where L is the total number of all ingredients for all recipes, S is the number of supplies, and K is the maximum string length. Building the graph takes O(L * K). The topological sort processes each supply and recipe once. The total number of edge traversals is L. Map and queue operations with strings take O(K). This is linear with respect to the size of the input.
Space
O((L + S + N) * K), where L is the total number of all ingredients for all recipes, S is the number of supplies, N is the number of recipes, and K is the maximum string length. The adjacency list can store up to L total ingredient dependencies. The in-degree map stores N recipes. The queue can store up to S supplies and N recipes. All keys and values are strings, contributing the K factor.
Trade-offs
Pros
Highly efficient, with linear time complexity relative to the input size.
Correctly handles complex dependencies and cycles.
It's a standard and robust approach for this category of problems.
Cons
More complex to conceptualize and implement compared to the simulation approach.
Requires understanding of graph theory and topological sorting.
Solutions
Solution
class Solution {public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) { Map<String, List<String>> g = new HashMap<>(); Map<String, Integer> indeg = new HashMap<>(); for (int i = 0; i < recipes.length; ++i) { for (String v : ingredients.get(i)) { g.computeIfAbsent(v, k->new ArrayList<>()).add(recipes[i]); } indeg.put(recipes[i], ingredients.get(i).size()); } Deque<String> q = new ArrayDeque<>(); for (String s : supplies) { q.offer(s); } List<String> ans = new ArrayList<>(); while (!q.isEmpty()) { for (int n = q.size(); n > 0; --n) { String i = q.pollFirst(); for (String j : g.getOrDefault(i, Collections.emptyList())) { indeg.put(j, indeg.get(j) - 1); if (indeg.get(j) == 0) { ans.add(j); q.offer(j); } } } } return ans; }}class Solution {public: vector<string> findAllRecipes(vector<string> &recipes, vector<vector<string>> &ingredients, vector<string> &supplies) { unordered_map<string, vector<string>> g; unordered_map<string, int> indeg; for (int i = 0; i < recipes.size(); ++i) { for (auto &v : ingredients[i]) { g[v].push_back(recipes[i]); } indeg[recipes[i]] = ingredients[i].size(); } queue<string> q; for (auto &s : supplies) { q.push(s); } vector<string> ans; while (!q.empty()) { for (int n = q.size(); n; --n) { auto i = q.front(); q.pop(); for (auto j : g[i]) { if (--indeg[j] == 0) { ans.push_back(j); q.push(j); } } } } return ans; }};class Solution: def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]: g = defaultdict(list) indeg = defaultdict(int) for a, b in zip(recipes, ingredients): for v in b: g[v]. append(a) indeg[a] += len(b) q = deque(supplies) ans = [] while q: for _ in range(len(q)): i = q . popleft() for j in g[i]: indeg[j] -= 1 if indeg[j] == 0: ans . append(j) q . append(j) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.