#2115

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find All Possible Recipes from Given Supplies

Determine all recipes you can prepare given initial supplies and ingredient dependencies, leveraging array scanning and hash lookups efficiently.

array hash table string graph topological sort

Problem Statement

You are given a list of recipes and the corresponding ingredients needed to make each recipe. Each recipe may depend on other recipes as ingredients, and you also have a set of initial supplies with unlimited quantities. Your goal is to find every recipe that can be prepared with the available supplies and the recipes you can generate along the way.

Return a list of all recipes that can be created in any order. Each ingredient and recipe name consists of lowercase English letters, all values are unique, and each recipe's ingredient list contains no duplicates. Efficiently checking ingredient availability is key, making array scanning with hash lookups the ideal pattern for this problem.

Examples

Example 1

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]

Output: ["bread"]

We can create "bread" since we have the ingredients "yeast" and "flour".

Example 2

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]

Output: ["bread","sandwich"]

We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Example 3

Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]

Output: ["bread","sandwich","burger"]

We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread". We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

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 only of lowercase English letters.
All the values of recipes and supplies combined are unique.
Each ingredients[i] does not contain any duplicate values.

Solution Approach

Map Recipes to Ingredients

Build a hash table mapping each recipe to its list of ingredients. This allows O(1) checks to see which ingredients are still missing while scanning through the recipes array.

Track Available Supplies

Maintain a hash set of all initial supplies and recipes you have successfully created. Iteratively scan the recipes array and add recipes to the set once all their ingredients are available, ensuring no recipe is processed before its prerequisites.

Iteratively Expand Possibilities

Repeat scanning until no new recipes can be added. This ensures all dependent recipes are considered in topological order without building an explicit graph. Return all recipes successfully added to the available set.

Complexity Analysis

Metric	Value
Time	O(n + m + s)
Space	O(n + m + s)

Time complexity is O(n + m + s), where n is the number of recipes, m is the total number of ingredient entries, and s is the number of initial supplies. Space complexity is O(n + m + s) for the hash tables storing recipes, ingredients, and available supplies.

What Interviewers Usually Probe

Can you efficiently track which ingredients are available without repeatedly scanning all recipes?
What data structure helps quickly determine if a needed ingredient exists in your current supplies?
How would you handle a recipe that depends on another recipe not yet created?

Common Pitfalls or Variants

Common pitfalls

Failing to account for recipes that depend on other recipes as ingredients, causing incorrect availability checks.
Re-scanning all recipes without updating the available ingredients set, leading to unnecessary repeated work.
Not using a hash set for supplies, resulting in O(n*m) lookups instead of O(1) checks per ingredient.

Follow-up variants

Count the number of possible recipes you can make rather than returning the list.
Given a target recipe, determine the minimal set of supplies needed to create it.
Handle recipes with circular dependencies and return only recipes that are safe to create.

FAQ

What pattern does 'Find All Possible Recipes from Given Supplies' use?

It uses array scanning combined with hash table lookups to efficiently track available ingredients and propagate newly creatable recipes.

Can the recipes be returned in any order?

Yes, the problem allows the output list to be in any order as long as all creatable recipes are included.

How do I handle a recipe that requires another recipe as an ingredient?

Treat each successfully created recipe as a new supply and iteratively check dependent recipes until no new recipes can be added.

What data structures are most effective for this problem?

A hash set for available supplies and a hash map for recipe to ingredient mapping ensures constant-time lookups and efficient scanning.

What is the main failure mode in this problem?

The main failure is prematurely checking recipes before all their dependent ingredients are available, which can lead to missing valid recipes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findAllRecipes(
        self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]
    ) -> List[str]:
        g = defaultdict(list)
        indeg = defaultdict(int)
        for a, b in zip(recipes, ingredients):
            for v in b:
                g[v].append(a)
            indeg[a] += len(b)
        q = supplies
        ans = []
        for i in q:
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    ans.append(j)
                    q.append(j)
        return ans

Continue Practicing

#2246 longest path with different adjacent characters #2131 longest palindrome by concatenating two letter words #2135 count words obtained after adding a letter