2115. Find All Possible Recipes from Given Supplies

MediumGraphTopological SortArrayHash TableString
Leetcode Link

Problem Description

In this problem, you are essentially a chef with a recipe book and a pantry with an infinite supply of some ingredients. The recipes array contains the names of recipes you can make. Each recipe requires a set of ingredients listed in the ingredients 2D array, where ingredients[i] corresponds to the recipes[i]. The twist is that some of the ingredients could themselves be recipes you need to prepare before you can use them in another recipe.

You also have a supplies array containing the ingredients initially available to you. The goal is to determine all the recipes that you can create using the supplies you have, along with any other recipe that can be made as an ingredient. It is possible for recipes to be interdependent, meaning one recipe may require another recipe as an ingredient and vice versa.

Intuition

To arrive at the solution, consider the problem as a dependency graph where each node represents an ingredient or a recipe, and each edge represents a requirement; that is, a recipe depends on its ingredients.

  • Begin by creating a directed graph g where an edge from ingredient v to recipe a means that 'a' requires 'v'. This is formed by zipping together recipes and ingredients.

  • Use a hashmap indeg (short for indegree) to keep track of how many ingredients are needed for each recipe to be created.

  • Initialize a queue q with the initial supplies. These are the starting points in the graph as you have an infinite supply of them.

  • For each ingredient i in the queue q, look at all the recipes j that depend on it (i.e., i is one of the ingredients of j). Decrease the indeg count for these recipes because you've just secured one of their required ingredients by depleting it from q.

  • If a recipe's indeg becomes zero, it means all its required ingredients are met, and the recipe can be created. Add this recipe to the list of answer ans and add it back to q because now that this recipe is created, it can act as an ingredient for other recipes.

  • Repeat this process until the queue is empty.

The intuition behind this approach lies in the technique known as topological sorting, where you determine an order of tasks to perform based on their dependencies. Here, you are using the indegrees and a queue to iteratively add recipes to your answer list as their dependencies are met. It also utilizes the concept of Breadth-First Search (BFS) — by using the queue, we are processing ingredients level by level, starting from those that are immediately available from the initial supplies.

Learn more about Graph and Topological Sort patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The implementation follows a strategy commonly used in problems involving dependency resolution, which aligns closely with topological sorting.

Here are the key components of the solution approach:

  • Graph Construction: This is achieved by associating each ingredient with the recipes it belongs to. defaultdict(list) is used to construct the directed graph g where for each ingredient v in every recipe a, we append a to g[v]. This indicates that a can only be made once v is available.

  • Tracking Dependencies: To track the number of remaining ingredients required to make a recipe, we use the indeg hashmap. This corresponds to the indegree of the recipe node in a graph. For every recipe, its indegree is incremented by the number of ingredients it needs, which is just the length of the corresponding list in ingredients.

  • Processing Using Queue: A queue q, specifically a deque, is used to perform a Breadth-First Search on the graph. We seed this queue with the initial supplies.

  • BFS Algorithm: We start processing items from the queue. For each supply (ingredient) i taken out from the front of the queue, we consider all recipes j that depend on i (j is in g[i]). For each of these recipes, we decrease their indeg value because one of their required ingredients is now available (used). When the indeg of a recipe j hits zero, it means all the ingredients for j have been "gathered," and we can add j to the resulting list ans. We then put j back into the queue because this recipe can now potentially be used as an ingredient for other recipes.

  • Storage for Results: The recipes that can be created are stored in the list ans. Whenever a recipe's indegree becomes zero, that recipe is added to ans.

The algorithm terminates when there are no more items left in the queue to process, ensuring that all possible recipes that can be made with the initial supplies and by creating other recipes have been included in ans.

This procedure effectively simulates building up your capability to create recipes as you gather or create the necessary ingredients, respecting the order in which the availability of ingredients allows the creation of new ones.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Imagine we are given the following data:

  • recipes = ["bread", "sandwich", "burger"]
  • ingredients = [["flour", "water"], ["bread", "ham"], ["sandwich", "cheese"]]
  • supplies = ["flour", "water", "cheese", "ham"]

First, let's construct the directed graph g:

  • g["flour"] will have ["bread"] because 'bread' requires 'flour'.
  • g["water"] will have ["bread"] because 'bread' also requires 'water'.
  • g["bread"] will have ["sandwich"] because 'sandwich' requires 'bread'.
  • g["ham"] will have ["sandwich"] because 'sandwich' requires 'ham'.
  • g["sandwich"] will have ["burger"] because 'burger' requires 'sandwich'.
  • g["cheese"] will have ["burger"] because 'burger' requires 'cheese'.

Next, we set up the indeg hashmap:

  • indeg["bread"] is 2 because 'bread' requires two ingredients: 'flour' and 'water'.
  • indeg["sandwich"] is 2 because 'sandwich' requires 'bread' and 'ham'.
  • indeg["burger"] is 2 because 'burger' requires 'sandwich' and 'cheese'.

Now, initialize the queue q with the initial supplies:

  • q will have ["flour", "water", "cheese", "ham"].

Start the Breadth-First Search algorithm:

  1. Dequeue 'flour' from q. Look at the recipes this ingredient belongs to, which is ["bread"]. Decrease indeg["bread"] by 1. Now indeg["bread"] is 1.

  2. Dequeue 'water' from q. 'bread' needs 'water', so decrease indeg["bread"] by 1 again. Now indeg["bread"] becomes 0. This means we can make 'bread'. Add 'bread' to ans and enqueue 'bread' into q.

  3. Dequeue 'cheese' from q. It doesn't lead to a recipe with a zero indegree yet, so move on.

  4. Dequeue 'ham' from q. 'sandwich' requires 'ham', so decrease indeg["sandwich"] by 1. Now indeg["sandwich"] is 1.

  5. Dequeue 'bread' from q (which was just made). 'sandwich' requires 'bread', so decrease indeg["sandwich"] by 1. Now indeg["sandwich"] becomes 0. This means we can make 'sandwich'. Add 'sandwich' to ans and enqueue 'sandwich' into q.

  6. Dequeue 'sandwich' from q. 'burger' requires 'sandwich', so decrease indeg["burger"] by 1. Now indeg["burger"] is 1.

  7. No more items in q can lead to a zero indegree.

The queue is now empty, and the BFS process is complete. The recipes that can be made are marked in the ans list which contains ["bread", "sandwich"]. Note that 'burger' can't be completed because we need a 'sandwich' that we've just used to make a 'sandwich' recipe and 'cheese'.

This example demonstrates each step of the algorithm in solving the problem, respecting the order of dependencies in the recipe-ingredient graph.

Solution Implementation

1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5    def findAllRecipes(
6        self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]
7    ) -> List[str]:
8        # Create a graph to map each ingredient to the recipes that require it
9        graph = defaultdict(list)
10      
11        # Dictionary to keep track of the number of pending ingredients for each recipe
12        incoming_edges = defaultdict(int)
13      
14        # Build the graph and update the incoming edges count for each recipe
15        for recipe, required_ingredients in zip(recipes, ingredients):
16            for ingredient in required_ingredients:
17                graph[ingredient].append(recipe)
18            incoming_edges[recipe] += len(required_ingredients)
19      
20        # Initialize a queue with the available supplies (ingredients)
21        queue = deque(supplies)
22      
23        # List to store the possible recipes we can cook
24        available_recipes = []
25      
26        # Process the queue until it's empty
27        while queue:
28            # Go through the current size of the queue (ingredients available at this level)
29            for _ in range(len(queue)):
30                ingredient = queue.popleft()
31                # Check each recipe that can be made with the current ingredient
32                for recipe in graph[ingredient]:
33                    # Decrease the count of pending ingredients for the current recipe
34                    incoming_edges[recipe] -= 1
35                    # If all ingredients for the recipe are available, add to the list
36                    if incoming_edges[recipe] == 0:
37                        available_recipes.append(recipe)
38                        # Add the newly available recipe to the queue
39                        queue.append(recipe)
40      
41        # Return the list of recipes we can cook with the available supplies
42        return available_recipes
43
1import java.util.*;
2
3class Solution {
4    public List<String> findAllRecipes(
5        String[] recipes, List<List<String>> ingredients, String[] supplies) {
6      
7        // Initialize a graph to represent ingredients pointing to recipes
8        Map<String, List<String>> graph = new HashMap<>();
9        // Initialize a map to store the indegree of each recipe
10        Map<String, Integer> indegreeMap = new HashMap<>();
11      
12        // Build the graph and indegree map
13        for (int i = 0; i < recipes.length; ++i) {
14            for (String ingredient : ingredients.get(i)) {
15                // Add the recipe to the list of recipes that the ingredient can make
16                graph.computeIfAbsent(ingredient, k -> new ArrayList<>()).add(recipes[i]);
17            }
18            // Set the initial indegree for the recipe based on number of ingredients required
19            indegreeMap.put(recipes[i], ingredients.get(i).size());
20        }
21      
22        // Queue to perform the topological sort
23        Deque<String> queue = new ArrayDeque<>();
24      
25        // Offer all initial supplies to the queue
26        for (String supply : supplies) {
27            queue.offer(supply);
28        }
29      
30        // List to store the available recipes to be returned
31        List<String> availableRecipes = new ArrayList<>();
32      
33        // Process the graph using BFS - topological sort approach
34        while (!queue.isEmpty()) {
35            int size = queue.size(); // Number of elements to process in current level
36          
37            // Process all nodes in the current level
38            for (int i = 0; i < size; ++i) {
39                // Poll an ingredient from the queue
40                String ingredient = queue.pollFirst();
41              
42                // Get all recipes that can be made with this ingredient
43                for (String recipe : graph.getOrDefault(ingredient, Collections.emptyList())) {
44                    // Decrease the indegree of the recipe
45                    indegreeMap.put(recipe, indegreeMap.get(recipe) - 1);
46                  
47                    // If the recipe's indegree is zero, it can be made with available ingredients
48                    if (indegreeMap.get(recipe) == 0) {
49                        availableRecipes.add(recipe);
50                        // Offer this recipe as a new available ingredient
51                        queue.offer(recipe);
52                    }
53                }
54            }
55        }
56      
57        // Return the list of available recipes
58        return availableRecipes;
59    }
60}
61
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <queue>
5
6using namespace std;
7
8class Solution {
9public:
10    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
11        // Create a graph to represent the dependencies.
12        unordered_map<string, vector<string>> dependencyGraph;
13        // This will keep track of the in-degrees of each recipe.
14        unordered_map<string, int> inDegrees;
15      
16        // Build the graph and initialize the in-degrees.
17        for (int i = 0; i < recipes.size(); ++i) {
18            for (const auto& ingredient : ingredients[i]) {
19                dependencyGraph[ingredient].push_back(recipes[i]);
20            }
21            inDegrees[recipes[i]] = ingredients[i].size();
22        }
23
24        // Initialize a queue with the initial supplies available.
25        queue<string> q;
26        for (const auto& supply : supplies) {
27            q.push(supply);
28        }
29
30        // This will hold the recipes that can be cooked.
31        vector<string> achievableRecipes;
32
33        // Process each supply to see if recipes can be made.
34        while (!q.empty()) {
35            int queueSize = q.size();
36            while (queueSize--) {
37                string ingredient = q.front(); // The current ingredient to process.
38                q.pop();
39
40                // Traverse the adjacency list of the current ingredient.
41                for (const auto& recipe : dependencyGraph[ingredient]) {
42                    // As we are able to cook with this ingredient, decrement the in-degree.
43                    // An in-degree of 0 implies all ingredients for this recipe are available.
44                    if (--inDegrees[recipe] == 0) {
45                        achievableRecipes.push_back(recipe); // Add the recipe to the answer list.
46                        q.push(recipe); // Add the recipe to the queue as a new potential ingredient.
47                    }
48                }
49            }
50        }
51      
52        // Return the list of recipes that can be cooked.
53        return achievableRecipes;
54    }
55};
56
1// Define the types for better type-checking and clarity
2type Recipe = string;
3type Ingredient = string;
4
5// Maps an ingredient to a list of recipes that require it.
6const dependencyGraph: Record<Ingredient, Recipe[]> = {};
7
8// Tracks the number of missing ingredients for each recipe.
9const inDegrees: Record<Recipe, number> = {};
10
11// Stores the initial supplies available.
12const suppliesQueue: Ingredient[] = [];
13
14// The recipes that can be cooked with the available ingredients.
15const achievableRecipes: Recipe[] = [];
16
17// Function to find all recipes that can be created with given ingredients and supplies.
18function findAllRecipes(recipes: Recipe[], ingredients: Ingredient[][], supplies: Ingredient[]): Recipe[] {
19    // Build the graph and initialize in-degrees
20    recipes.forEach((recipe, i) => {
21        ingredients[i].forEach((ingredient) => {
22            if (!dependencyGraph[ingredient]) {
23                dependencyGraph[ingredient] = [];
24            }
25            dependencyGraph[ingredient].push(supplies);
26        });
27        inDegrees[recipe] = ingredients[i].length;
28    });
29
30    // Initialize the queue with the initial supplies
31    supplies.forEach((supply) => suppliesQueue.push(supply));
32
33    // Process the supplies to see which recipes can be made
34    while (suppliesQueue.length > 0) {
35        const ingredient = suppliesQueue.shift(); // Take the first supply/ingredient from the queue
36
37        if (dependencyGraph[ingredient]) {
38            dependencyGraph[ingredient].forEach((recipe) => {
39                // Reduce the missing ingredient count (in-degree) for the recipe
40                inDegrees[recipe] -= 1;
41
42                // If all ingredients for a recipe are available, add the recipe to the list and the queue
43                if (inDegrees[recipe] === 0) {
44                    achievableRecipes.push(recipe);
45                    suppliesQueue.push(recipe); // Now available as an ingredient
46                }
47            });
48        }
49    }
50
51    // Return the list of recipes that can be cooked
52    return achievableRecipes;
53}
54
55// To use the function, you would call it with the recipes, ingredients, and supplies
56// For example:
57// const recipes = ["bread"];
58// const ingredients = [["flour", "water"]];
59// const supplies = ["flour", "water"];
60// const result = findAllRecipes(recipes, ingredients, supplies);
61
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the findAllRecipes function is O(N + M + V) where:

  • N is the number of supplies.
  • M is the number of recipes.
  • V is the total number of ingredients across all recipes.

Here's why:

  • Building the graph with adjacency lists takes O(V) time, as you must process each ingredient of each recipe.
  • Filling the indegree map also takes O(V) time.
  • The breadth-first search (BFS) queue processing would be O(N + M) at most since each supply is put into the queue exactly once at the start, and then each recipe can only be put into the queue at most once when its indegree reaches zero.
  • Within the BFS, for each item, you look at its adjacency list and update indegrees. In total, across all BFS steps, you will examine and decrement each edge in the adjacency list only once. There are V edges since each edge corresponds to a unique ingredient in a recipe.

Space Complexity

The space complexity of the given code is O(N + M + V). The factors contributing to the space complexity include:

  • The queue can grow up to a maximum of the number of supplies plus recipes, O(N + M).
  • The graph g and indegree map indeg both combined will take up space proportional to the number of unique ingredients plus recipes, which is O(M + V).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫