DSA problem
Find All Possible Recipes from Given Supplies
You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The i-th recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. An ingredient 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 each. 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 (a cycle), in which case neither can be cooked unless its other prerequisites are independently satisfied.
The cleanest formulation is a directed graph: there is an edge ingredient -> recipe for every entry in ingredients[i]. The "in-degree" of a recipe is the number of distinct ingredients it still lacks. Supplies are nodes with in-degree zero by definition (they require nothing), so we kick off Kahn's BFS by enqueuing every supply.
While the queue is non-empty, pop an ingredient u, look at every recipe r that lists u as an ingredient, decrement r's missing-ingredient count, and enqueue r if it falls to zero — meaning every ingredient r needs is now available. Recipes that are never enqueued either depend on something we never had or sit inside a dependency cycle, so they are excluded. Total work is O(n + total ingredients).
Examples
recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]["bread"]recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]["bread","sandwich"]recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]["bread","sandwich","burger"]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 of only lowercase English letters.
- All the values of recipes and supplies combined are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.