Find All Possible Recipes from Given Supplies
Find All Possible Recipes from Given Supplies is a medium graphs problem solved with the topological sort pattern.
The best approach, optimal (kahn's topological sort from the supplies), runs in O(n · k + s) time and O(n · k + s) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeat sweeps until stable) up.
Problem
You are planning a menu. recipes[i] is the name of a dish, and ingredients[i] lists every item needed to make it. The list supplies holds items you have in unlimited quantity from the start.
An ingredient can itself be another recipe: once you can make a recipe, it is available as an ingredient for other recipes, also without limit.
Return the names of all recipes you are able to make, in any order.
Examples
Example 1
- Input
recipes = ["toast","sandwich"], ingredients = [["bread","butter"],["toast","cheese"]], supplies = ["bread","butter","cheese"]- Output
["toast","sandwich"]- Why
- Toast needs only supplies. Once toast exists, the sandwich has toast and cheese.
Example 2
- Input
recipes = ["tea","chai"], ingredients = [["leaves","water"],["tea","milk","spice"]], supplies = ["leaves","water","milk"]- Output
["tea"]- Why
- Tea can be made, but nobody supplies spice, so chai is out.
Example 3
- Input
recipes = ["dough","starter"], ingredients = [["starter","flour"],["dough"]], supplies = ["flour"]- Output
[]- Why
- Each recipe needs the other first, so neither can ever be made.
Constraints
n == recipes.length == ingredients.length,1 <= n <= 1001 <= ingredients[i].length, supplies.length <= 100- Every name is 1 to 10 lowercase English letters.
- All names in
recipesandsuppliestogether are distinct, and no ingredient appears twice in the sameingredients[i].
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (repeat sweeps until stable) | O(n² · k) | O(n + s) |
| Optimal (Kahn's topological sort from the supplies) | O(n · k + s) | O(n · k + s) |
1Brute force (repeat sweeps until stable)
O(n² · k)Up to n sweeps (one per new recipe), each checking n recipes with up to k ingredients.O(n + s)The available set holds supplies and made recipes.Put all supplies in a set of available items. Sweep over the recipes; whenever a not-yet-made recipe has all its ingredients available, make it and add it to the set. Repeat sweeps until one sweep makes nothing.
- available = set(supplies); made = boolean per recipe.
- Loop: changed = false; for each unmade recipe i whose ingredients are all in available: mark it, add it to available and to the answer, changed = true.
- Stop when changed is false.
class Solution {
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Set<String> available = new HashSet<>(Arrays.asList(supplies));
boolean[] made = new boolean[recipes.length];
List<String> res = new ArrayList<>();
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i < recipes.length; i++) {
if (made[i]) continue;
boolean ok = true;
for (String ing : ingredients.get(i))
if (!available.contains(ing)) { ok = false; break; }
if (ok) {
made[i] = true;
available.add(recipes[i]);
res.add(recipes[i]);
changed = true;
}
}
}
return res;
}
}class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
available = set(supplies)
made = [False] * len(recipes)
res = []
changed = True
while changed:
changed = False
for i in range(len(recipes)):
if made[i]:
continue
if all(ing in available for ing in ingredients[i]):
made[i] = True
available.add(recipes[i])
res.append(recipes[i])
changed = True
return resclass Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
unordered_set<string> available(supplies.begin(), supplies.end());
vector<bool> made(recipes.size(), false);
vector<string> res;
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i < (int)recipes.size(); i++) {
if (made[i]) continue;
bool ok = true;
for (auto& ing : ingredients[i])
if (!available.count(ing)) { ok = false; break; }
if (ok) {
made[i] = true;
available.insert(recipes[i]);
res.push_back(recipes[i]);
changed = true;
}
}
}
return res;
}
};function findAllRecipes(recipes, ingredients, supplies) {
const available = new Set(supplies);
const made = new Array(recipes.length).fill(false);
const res = [];
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i < recipes.length; i++) {
if (made[i]) continue;
if (ingredients[i].every((ing) => available.has(ing))) {
made[i] = true;
available.add(recipes[i]);
res.push(recipes[i]);
changed = true;
}
}
}
return res;
}2Optimal (Kahn's topological sort from the supplies)
O(n · k + s)Each edge is followed once and each name is queued at most once.O(n · k + s)The adjacency lists hold one entry per (ingredient, recipe) pair.Build a graph with an edge from every ingredient name to each recipe that uses it, and give each recipe an in-degree equal to its number of ingredients. Start a queue with all supplies. Popping an item satisfies one ingredient of each recipe that uses it; when a recipe's in-degree reaches 0 it is made, recorded, and pushed so it can unlock later recipes. Missing ingredients and cycles simply never reach 0.
- For each recipe i: indeg[recipes[i]] = ingredients[i].size(); for each ingredient add edge ingredient -> recipes[i].
- queue = all supplies.
- Pop x; for each recipe r in users[x]: indeg[r]--; if it becomes 0, add r to the answer and push r.
- Return the answer.
class Solution {
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Map<String, List<String>> users = new HashMap<>();
Map<String, Integer> indeg = new HashMap<>();
for (int i = 0; i < recipes.length; i++) {
indeg.put(recipes[i], ingredients.get(i).size());
for (String ing : ingredients.get(i))
users.computeIfAbsent(ing, k -> new ArrayList<>()).add(recipes[i]);
}
ArrayDeque<String> q = new ArrayDeque<>(Arrays.asList(supplies));
List<String> res = new ArrayList<>();
while (!q.isEmpty()) {
String x = q.poll();
for (String r : users.getOrDefault(x, Collections.emptyList())) {
int d = indeg.get(r) - 1;
indeg.put(r, d);
if (d == 0) {
res.add(r);
q.add(r);
}
}
}
return res;
}
}class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
users = defaultdict(list)
indeg = {}
for i, r in enumerate(recipes):
indeg[r] = len(ingredients[i])
for ing in ingredients[i]:
users[ing].append(r)
q = deque(supplies)
res = []
while q:
x = q.popleft()
for r in users.get(x, []):
indeg[r] -= 1
if indeg[r] == 0:
res.append(r)
q.append(r)
return resclass Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
unordered_map<string, vector<string>> users;
unordered_map<string, int> indeg;
for (int i = 0; i < (int)recipes.size(); i++) {
indeg[recipes[i]] = ingredients[i].size();
for (auto& ing : ingredients[i]) users[ing].push_back(recipes[i]);
}
queue<string> q;
for (auto& s : supplies) q.push(s);
vector<string> res;
while (!q.empty()) {
string x = q.front();
q.pop();
auto it = users.find(x);
if (it == users.end()) continue;
for (auto& r : it->second) {
if (--indeg[r] == 0) {
res.push_back(r);
q.push(r);
}
}
}
return res;
}
};function findAllRecipes(recipes, ingredients, supplies) {
const users = new Map();
const indeg = new Map();
for (let i = 0; i < recipes.length; i++) {
indeg.set(recipes[i], ingredients[i].length);
for (const ing of ingredients[i]) {
if (!users.has(ing)) users.set(ing, []);
users.get(ing).push(recipes[i]);
}
}
const q = [...supplies];
let head = 0;
const res = [];
while (head < q.length) {
const x = q[head++];
for (const r of users.get(x) || []) {
const d = indeg.get(r) - 1;
indeg.set(r, d);
if (d === 0) {
res.push(r);
q.push(r);
}
}
}
return res;
}Edge cases to test
- An ingredient that is neither a supply nor a recipe (that recipe and everything built on it fail)
- Recipes that depend on each other in a cycle
- A long chain where each recipe needs the previous one
- Recipes listed before the recipes they depend on
- No recipe can be made at all
Hints
Hint 1
A recipe can be made once every one of its ingredients is available, and a freshly made recipe becomes available for others.
Hint 2
You could keep sweeping over the recipes until a sweep makes nothing new, but that may need up to n sweeps.
Hint 3
Treat it as a graph: an edge from each ingredient to the recipe that uses it. A recipe is ready when all its incoming edges are satisfied, which is exactly Kahn's topological sort starting from the supplies.
FAQ
What is the best time complexity for Find All Possible Recipes from Given Supplies?
Optimal (Kahn's topological sort from the supplies) runs in O(n · k + s) time and O(n · k + s) extra space. Each edge is followed once and each name is queued at most once.
Which pattern does Find All Possible Recipes from Given Supplies use?
It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.
Is there a brute force solution for Find All Possible Recipes from Given Supplies?
Yes. Brute force (repeat sweeps until stable) takes O(n² · k) time and O(n + s) space. Put all supplies in a set of available items.
Which edge cases should I test for Find All Possible Recipes from Given Supplies?
An ingredient that is neither a supply nor a recipe (that recipe and everything built on it fail); Recipes that depend on each other in a cycle; A long chain where each recipe needs the previous one; Recipes listed before the recipes they depend on; No recipe can be made at all.