Leetcode 2115: Find All Possible Recipes from Given Supplies

In this problem, we are trying to figure the list of recipes that we can make out of a list of ingredients in unlimited quantity. The difficulty comes from the fact that in the list of ingredients necessary for each recipe, there can be another recipe itself.

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]. Ingredients to a recipe may need to be created from 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.

The last note: “Note that two recipes may contain each other in their ingredients” tells us there can be mutual dependencies, that we can interpret as loops in the dependency graph.

For this problem, I tried to comment my code as much as possible so that the code speaks by itself. However, I still think a short explanation is needed.

First, we need to transform the input data so that it is more practical for the problem that we are trying to solve. In particular, when we are given arrays for which the order of elements doesn’t matter, changing them to Sets or Maps makes the most sense, in particular here when we want to do a lot of lookups by using the String values.

Therefore I changed the supplies to a Set, changed the recipes to a Map of recipe name to there original index.

Then I opted for a simple recursive approach, I can make a recipe r if I can make all of the ingredients, for the ingredients which are recipes, I make the recursive call to know if they are possible to make. This recursion could be infinite in the case of mutual dependency. So I set up the algorithm so that when we encounter a loop, we set all the recipes in the loop to be impossible.

I also added caching, so that it isn’t necessary to repeat computation that was already done. This make the algorithm O(n + m + k) where n is the number of recipes, m the number elements in supplies, k is the number of elements in…