Editorial
Core insight
Find All Possible Recipes from Given Supplies · Graph Traversal Patterns (DFS & BFS)
Core Insight for Find All Possible Recipes from Given Supplies
The key intuition is to view ingredients and recipes as nodes in a graph. The relationship "Recipe A requires Ingredient B" can be modeled as a directed edge from B to A (). This direction signifies that having B contributes to unlocking A.
Using this model, the problem transforms into finding all nodes that can be reached and "processed" starting from the initial set of zero-dependency nodes (the supplies).
Key Mapping to Kahn's Algorithm:
- In-Degree: The number of ingredients a recipe is currently missing.
- Graph Edges: An adjacency list where a key is an ingredient (or a recipe acting as an ingredient) and the values are the recipes that require it.
- Queue: A processing queue initially populated with the given
supplies.
By processing the supplies, we "unlock" dependencies. Every time we process an item, we look at the recipes that need it and decrement their in-degree count. If a recipe's in-degree drops to 0, it means all its ingredients are available. We then add this recipe to the queue, allowing it to unlock further recipes.
This approach efficiently handles cascades of recipes (e.g., Bread Sandwich Burger) and naturally handles cycles (e.g., A needs B, B needs A) by simply never reducing their in-degrees to zero.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 2115: Find All Possible Recipes from Given Supplies Solution & Explanation
Problem Overview
TL;DR: Model the recipes and ingredients as a directed graph and perform a Topological Sort (Kahn's Algorithm) to determine which recipes can be completed starting from the initial supplies.
The problem asks us to determine which recipes can be created given a set of initial supplies and a list of dependencies (ingredients) for each recipe. A crucial detail is that a created recipe can subsequently be used as an ingredient for another recipe. This creates a chain of dependencies. We need to return all recipes that can eventually be created.
This is a classic dependency resolution problem, making "LeetCode 2115" a standard application of graph theory concepts, specifically designed to test understanding of directed acyclic graphs (DAGs) and order of execution.
Brute Force Approach for Find All Possible Recipes from Given Supplies
The naive approach attempts to simulate the creation process iteratively. We can maintain a set of currently available items (initially just the supplies). In each iteration, we loop through every recipe that hasn't been created yet. For each recipe, we check if all its required ingredients exist in our available set. If they do, we mark the recipe as created, add it to the available set, and repeat the process.
We continue these iterations until a full pass over the recipes results in no new creations.
1# Pseudo-code for Brute Force
2available = set(supplies)
3created_recipes = []
4changed = True
5
6while changed:
7 changed = False
8 for i in range(len(recipes)):
9 if recipe[i] not in available:
10 if all(ingredient in available for ingredient in ingredients[i]):
11 available.add(recipe[i])
12 created_recipes.append(recipe[i])
13 changed = TrueWhy this approach is suboptimal: The time complexity is roughly , where is the number of recipes and is the total number of ingredients across all recipes. In the worst-case scenario (a long chain where Recipe A allows Recipe B, which allows Recipe C, etc.), we might iterate through the list of recipes times. For large inputs, this redundant checking leads to Time Limit Exceeded (TLE) or poor performance compared to linear solutions.
Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)
We will implement Kahn's Algorithm to solve this problem efficiently.
-
Graph Construction:
- Create an adjacency list (graph) where
graph[item]contains a list of recipes that requireitem. - Create an
in_degreemap wherein_degree[recipe]stores the count of ingredients needed for that recipe.
- Create an adjacency list (graph) where
-
Initialization:
- Populate the
graphandin_degreemap by iterating through therecipesandingredientsinput arrays. - Initialize a queue (specifically a Deque in Python/Java or
std::queuein C++) with the initialsupplies. These are our starting nodes with effectively "zero unmet dependencies."
- Populate the
-
BFS Traversal:
- While the queue is not empty:
- Dequeue the current item (ingredient or created recipe).
- Iterate through all neighbors in
graph[current_item](recipes that need this item). - Decrement the
in_degreeof each neighbor. - Constraint Check: If a neighbor's
in_degreebecomes 0, it means the recipe is now possible. Add it to the queue and to our result list.
- While the queue is not empty:
-
Output:
- Return the list of created recipes.
Execution Flow
Let's trace the algorithm with a simple example:
recipes = ["bread", "sandwich"], ingredients = [["flour"], ["bread", "meat"]], supplies = ["flour", "meat"].
-
Build Graph & In-Degrees:
in_degree:{"bread": 1, "sandwich": 2}graph:{"flour": ["bread"], "bread": ["sandwich"], "meat": ["sandwich"]}
-
Initialize Queue:
- Queue contains
["flour", "meat"](from supplies).
- Queue contains
-
Process "flour":
- Pop "flour".
- Neighbors of "flour":
["bread"]. - Decrement
in_degree["bread"]from 1 to 0. in_degree["bread"]is 0. Add "bread" to Queue and Result.- Queue:
["meat", "bread"]. Result:["bread"].
-
Process "meat":
- Pop "meat".
- Neighbors of "meat":
["sandwich"]. - Decrement
in_degree["sandwich"]from 2 to 1. - Queue:
["bread"].
-
Process "bread":
- Pop "bread".
- Neighbors of "bread":
["sandwich"]. - Decrement
in_degree["sandwich"]from 1 to 0. in_degree["sandwich"]is 0. Add "sandwich" to Queue and Result.- Queue:
["sandwich"]. Result:["bread", "sandwich"].
-
Process "sandwich":
- Pop "sandwich".
- Neighbors: None.
- Queue empty.
-
Final Output:
["bread", "sandwich"].
Proof of Correctness
The algorithm is correct based on the invariant of Topological Sort. A node (recipe) is only added to the queue when its in-degree reaches zero. The in-degree represents the count of unsatisfied dependencies.
- Base Case: We start with supplies, which are items that exist unconditionally (dependencies satisfied).
- Inductive Step: When we process an item , we effectively "supply" it to all recipes that depend on . Decrementing the in-degree of correctly reflects that one less ingredient is needed.
- Termination: A recipe is added to the result set if and only if all its specific ingredients have been processed.
- Cycle Handling: If a set of recipes forms a cycle (A needs B, B needs A), their in-degrees will never reach zero because the dependencies are circular. They will correctly remain unvisited.
Pattern Reuse Notes
The Graph BFS - Topological Sort pattern is versatile and appears in many "dependency resolution" problems.
- LeetCode 207: Course Schedule: Determines if all courses can be finished. This is exactly checking if a valid Topological Sort exists (i.e., no cycles).
- LeetCode 210: Course Schedule II: Requires returning the actual order of courses. This is identical to returning the processing order in Kahn's algorithm.
- LeetCode 269: Alien Dictionary: Uses Topological Sort to determine the lexicographical order of characters based on word precedence.
- LeetCode 310: Minimum Height Trees: Uses a variation of Topological Sort (peeling an onion) by removing leaf nodes (degree 1) layer by layer.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 2115
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5#include <queue>
6
7using namespace std;
8
9class Solution {
10public:
11 vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
12 // Graph: ingredient -> list of recipes that need it
13 unordered_map<string, vector<string>> graph;
14 // In-degree: recipe -> count of missing ingredients
15 unordered_map<string, int> in_degree;
16
17 // Initialize in-degrees for all recipes
18 for (const string& recipe : recipes) {
19 in_degree[recipe] = 0;
20 }
21
22 // Build the graph
23 for (int i = 0; i < recipes.size(); ++i) {
24 string recipe = recipes[i];
25 for (const string& ingredient : ingredients[i]) {
26 graph[ingredient].push_back(recipe);
27 in_degree[recipe]++;
28 }
29 }
30
31 // Queue for Kahn's Algorithm, initialized with supplies
32 queue<string> q;
33 for (const string& supply : supplies) {
34 q.push(supply);
35 }
36
37 vector<string> result;
38
39 while (!q.empty()) {
40 string current = q.front();
41 q.pop();
42
43 // If current item is a recipe (and not just a raw supply), add to result
44 // Note: We can check if it was in the original recipes list,
45 // or simply rely on the flow since supplies are not recipes.
46 // However, the problem asks for recipes specifically.
47 // A simple check is if it's in our in_degree map.
48 if (in_degree.find(current) != in_degree.end()) {
49 result.push_back(current);
50 }
51
52 // Unlock neighbors
53 if (graph.find(current) != graph.end()) {
54 for (const string& neighbor : graph[current]) {
55 in_degree[neighbor]--;
56 if (in_degree[neighbor] == 0) {
57 q.push(neighbor);
58 }
59 }
60 }
61 }
62
63 return result;
64 }
65};Java Solution for LeetCode 2115
1import java.util.*;
2
3class Solution {
4 public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
5 // Graph: ingredient -> list of recipes dependent on it
6 Map<String, List<String>> graph = new HashMap<>();
7 // In-degree: recipe -> number of ingredients needed
8 Map<String, Integer> inDegree = new HashMap<>();
9
10 // Initialize in-degree for all recipes
11 for (String recipe : recipes) {
12 inDegree.put(recipe, 0);
13 }
14
15 // Build graph and calculate in-degrees
16 for (int i = 0; i < recipes.length; i++) {
17 String recipe = recipes[i];
18 List<String> neededIngredients = ingredients.get(i);
19
20 for (String ingredient : neededIngredients) {
21 graph.putIfAbsent(ingredient, new ArrayList<>());
22 graph.get(ingredient).add(recipe);
23 inDegree.put(recipe, inDegree.get(recipe) + 1);
24 }
25 }
26
27 // Queue for BFS, initialized with supplies
28 Queue<String> queue = new LinkedList<>();
29 for (String supply : supplies) {
30 queue.offer(supply);
31 }
32
33 List<String> result = new ArrayList<>();
34
35 while (!queue.isEmpty()) {
36 String current = queue.poll();
37
38 // If the graph contains dependencies for this item
39 if (graph.containsKey(current)) {
40 for (String neighbor : graph.get(current)) {
41 inDegree.put(neighbor, inDegree.get(neighbor) - 1);
42
43 if (inDegree.get(neighbor) == 0) {
44 queue.offer(neighbor);
45 result.add(neighbor);
46 }
47 }
48 }
49 }
50
51 return result;
52 }
53}Python Solution for LeetCode 2115
1from collections import deque, defaultdict
2from typing import List
3
4class Solution:
5 def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
6 # Graph: ingredient -> list of recipes that need it
7 graph = defaultdict(list)
8 # In-degree: recipe -> count of missing ingredients
9 in_degree = {recipe: 0 for recipe in recipes}
10
11 # Build graph
12 for recipe, ing_list in zip(recipes, ingredients):
13 for ing in ing_list:
14 graph[ing].append(recipe)
15 in_degree[recipe] += 1
16
17 # Initialize queue with supplies
18 queue = deque(supplies)
19 result = []
20
21 while queue:
22 current = queue.popleft()
23
24 # If current item unlocks any recipes
25 if current in graph:
26 for neighbor in graph[current]:
27 in_degree[neighbor] -= 1
28 if in_degree[neighbor] == 0:
29 queue.append(neighbor)
30 result.append(neighbor)
31
32 return result