Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4
5

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:

1
2
3
4
5
6

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.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

Method 1 - Using Topological Sort

We can use a Directed Acyclic Graph (DAG) approach:

  1. Initial Setup:
    • Treat each recipe as a node, and add a directed edge from a recipe node to the nodes representing its ingredients (if they are recipes).
    • Use a map to store in-degrees for each recipe (i.e., how many unfulfilled prerequisites there are).
  2. Topological Sort:
    • Add all elements from supplies into an initial queue, since they can be directly used to create recipes.
    • Begin processing recipes:
      • If all ingredients for a recipe are satisfied, add the recipe to the queue (marking it as “created”).
    • Continue until the queue is empty.
  3. Result:
    • Collect all recipes that can be created during the process.

This approach ensures cyclic dependencies are avoided and recipes are created in logical order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> inDegrees = new HashMap<>();
        List<String> ans = new ArrayList<>();

        for (String recipe : recipes) {
            inDegrees.put(recipe, 0);
        }

        for (int i = 0; i < recipes.length; i++) {
            String recipe = recipes[i];
            for (String ingr : ingredients.get(i)) {
                graph.computeIfAbsent(ingr, k -> new ArrayList<>()).add(recipe);
                inDegrees.put(recipe, inDegrees.getOrDefault(recipe, 0) + 1);
            }
        }
        
        Queue<String> queue = new LinkedList<>(Arrays.asList(supplies));
        
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            if (inDegrees.containsKey(curr) && inDegrees.get(curr) == 0) {
                ans.add(curr);
            }

            for (String next : graph.getOrDefault(curr, new ArrayList<>())) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0) {
                    queue.add(next);
                }
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        graph = defaultdict(list)
        in_degrees = defaultdict(int)
        
        for r, ing in zip(recipes, ingredients):
            for item in ing:
                graph[item].append(r)
                in_degrees[r] += 1

        queue = deque(supplies)
        ans = []

        while queue:
            curr = queue.popleft()
            if curr in recipes:  # Add the current recipe if it can be made
                ans.append(curr)

            for next_recipe in graph[curr]:
                in_degrees[next_recipe] -= 1
                if in_degrees[next_recipe] == 0:
                    queue.append(next_recipe)

        return ans

Complexity

  • ⏰ Time complexity: O(n + sum(len(ingredients[i]))). Constructing the graph takes O(sum(len(ingredients[i]))), iterating through recipes is O(n), and processing recipes in the queue is O(sum(len(ingredients[i]))). Hence, total time complexity is O(n + sum(len(ingredients[i]))).
  • 🧺 Space complexity: O(n + sum(len(ingredients[i]))) for using data structures (graph + queue + visited set).