Medium · Graphs

Find All Possible Recipes from Given Supplies

Given n recipe names, where ingredients[i] lists everything recipes[i] needs, and a list of supplies available in unlimited amounts, return every recipe you can create, in any order. A recipe's ingredients may include other recipes, which become available once you have made them.

Examples

Example 1

{
  "recipes": ["bread", "sandwich"],
  "ingredients": [
    ["yeast", "flour"],
    ["bread", "meat"]
  ],
  "supplies": ["yeast", "flour", "meat"]
}

Output: made 2

Example 2

{
  "recipes": ["burger", "sandwich", "bread", "cake", "pie"],
  "ingredients": [
    ["sandwich", "meat", "bread"],
    ["bread", "meat"],
    ["yeast", "flour"],
    ["pie", "sugar"],
    ["cake", "flour"]
  ],
  "supplies": ["yeast", "flour", "meat", "sugar"]
}

Output: made 3

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.