Find All Possible Recipes From Given Supplies - Leetcode Solution

Problem Statement:

Given a list of supplies (ingredients) that you have in your pantry and a list of recipes, return an array of all the recipes that you can make, with the ingredients that you have.

Example:

Supplies: ["flour", "sugar", "eggs"] Recipes:

• Pancakes: flour, sugar, eggs, milk
• Brownies: flour, sugar, eggs, cocoa powder, oil

Output: ["Pancakes"]

Explanation: You have all the ingredients for pancakes but do not have the cocoa powder and oil which is needed for brownies.

Solution:

The problem can be solved by iterating over the list of recipes and checking if all the ingredients for each recipe are present in the supplies list. If all the ingredients are present, the recipe is added to the output list.

The following steps can be followed to implement the algorithm in Python:

Step 1: Create a dictionary to store the supplies and their counts.

Step 2: Iterate over the supply list and increment the count for each ingredient in the dictionary.

Step 3: Create an empty list to store the output.

Step 4: Iterate over the recipe list and for each recipe, check if all the ingredients are present in the supplies dictionary. If all ingredients are present, add the recipe to the output list.

Step 5: Return the output list.

The Python code for the above algorithm is given below:

class Solution: def findRecipes(self, supplies: List[str], recipes: List[List[str]]) -> List[str]: supplies_dict = {} for item in supplies: if item not in supplies_dict: supplies_dict[item] = 1 else: supplies_dict[item] += 1

    output = []
    for recipe in recipes:
        present = True
        for item in recipe:
            if item not in supplies_dict or supplies_dict[item] == 0:
                present = False
                break
            else:
                supplies_dict[item] -= 1
        if present:
            output.append(recipe[0])
        for item in recipe:
            supplies_dict[item] += 1
    
    return output

The time complexity of the above algorithm is O(n*m), where n is the size of the supplies list and m is the size of the recipes list. The space complexity is O(n) where n is the number of different supplies in the supplies list.

1