Find All Possible Recipes from Given Supplies
Medium · Graphs · Array · Hash Table · String · Graph · Topological Sort
Problem
You know how to cook n recipes. Recipe recipes[i] needs every item listed in ingredients[i]. An ingredient may itself be one of the recipes, in which case that recipe must be cooked first. You also start with an unlimited amount of every item in supplies.
Return the names of all recipes you are able to cook, in any order. Recipes may depend on each other, even in a cycle; a recipe caught in a cycle can never be made.
Examples
Input: recipes = ["toast","sandwich"], ingredients = [["bread"],["toast","cheese"]], supplies = ["bread","cheese"] Output: ["toast","sandwich"]
Toast needs only bread. Once toast exists, the sandwich can be made too.
Input: recipes = ["soup"], ingredients = [["water","salt"]], supplies = ["water"] Output: []
There is no salt anywhere.
Input: recipes = ["ab","cd"], ingredients = [["cd"],["ab"]], supplies = [] Output: []
Each recipe needs the other, so neither can be started.
Constraints
- n == len(recipes) == len(ingredients)
- 1 <= n <= 100
- 1 <= len(ingredients[i]) <= 100
- 0 <= len(supplies) <= 100
- Every name has 1 to 10 lowercase English letters or digits
- recipes and supplies together hold no duplicates, and no ingredients[i] holds duplicates
Approaches
- Rescan until nothing changes — time O(n · m), space O(n)
Follow-up
What if a supply can run out, say each supply has a limited count and each recipe uses one of each ingredient? Then cooking order matters and choices compete for the same items: it stops being a reachability question and becomes a search or flow problem.
Related problems
Start free on Cariara · Coding problems · System design studio
