LeetCode 2115 - Find All Possible Recipes from Given Supplies

This problem asks us to determine which recipes can be created when we start with a set of available supplies and are allowed to recursively create additional recipes. Each recipe has a list of required ingredients.

leetcodemediumarrayhash-tablestringgraph-theorytopological-sort

LeetCode Problem 2115

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem asks us to determine which recipes can be created when we start with a set of available supplies and are allowed to recursively create additional recipes.

Each recipe has a list of required ingredients. Some ingredients are basic supplies that we already own, while others may themselves be recipes. Once a recipe becomes creatable, it effectively turns into a new available supply that can help create additional recipes.

The input consists of three arrays:

  • recipes[i] is the name of the i-th recipe.
  • ingredients[i] contains all ingredients needed to create recipes[i].
  • supplies contains ingredients initially available in unlimited quantity.

The goal is to return every recipe that can eventually be created.

The important detail is that recipes can depend on other recipes. For example:

  • "sandwich" may require "bread"
  • "bread" may itself be a recipe requiring "yeast" and "flour"

If we can create "bread", then "bread" becomes available for creating "sandwich".

The problem also mentions that recipes may form cycles. For example:

  • "A" requires "B"
  • "B" requires "A"

Such recipes cannot be created unless one of them is already available as a supply.

The constraints are relatively small, with at most 100 recipes and 100 supplies, but the dependency structure naturally forms a graph. Even though brute force may pass under these limits, the intended solution is graph-based and uses topological sorting.

Several edge cases are important:

  • Recipes whose ingredients are already fully available from supplies.
  • Recipes depending on other recipes multiple levels deep.
  • Cyclic dependencies that can never be resolved.
  • Ingredients that are neither supplies nor recipes.
  • Independent recipe chains that do not interact.

The problem guarantees that recipe names and supply names are unique, and each ingredient list contains no duplicates.

Approaches

Brute Force Approach

A straightforward solution repeatedly scans all recipes and checks whether every ingredient for a recipe is currently available.

We begin with a set containing all supplies. Then:

  1. Iterate through every recipe.
  2. If all ingredients of a recipe are available, add the recipe itself into the available set.
  3. Repeat the process until no new recipe can be added.

This works because recipes gradually become available as their dependencies are resolved. Eventually, the system stabilizes when no additional recipes can be created.

The main problem with this method is inefficiency. We repeatedly recheck recipes whose dependencies are still unavailable. In the worst case, many unnecessary scans occur before the final result stabilizes.

Although the constraints are small enough that this may pass, it is not optimal and does not scale well.

Optimal Approach, Graph + Topological Sort

The key insight is that this problem is fundamentally a dependency graph problem.

A recipe depends on its ingredients. When an ingredient becomes available, it helps unlock recipes that require it.

This is very similar to topological sorting:

  • Each ingredient points to recipes that depend on it.
  • Each recipe tracks how many required ingredients are still missing.
  • When all required ingredients become available, the recipe becomes creatable.

We can model this using:

  • A graph from ingredient → recipes that need it.
  • An indegree count representing how many ingredients each recipe still requires.
  • A queue containing currently available items.

Initially:

  • All supplies are inserted into the queue.
  • Whenever an item becomes available, we reduce dependency counts for recipes requiring it.
  • If a recipe's remaining dependency count becomes zero, that recipe is now creatable and is added to the queue.

This efficiently processes dependencies exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(R² × I) O(R + S) Repeatedly rescans recipes until stabilization
Optimal O(R × I) O(R × I) Uses graph traversal and topological sorting

Where:

  • R = number of recipes
  • I = average number of ingredients
  • S = number of supplies

Algorithm Walkthrough

Step 1, Build the Dependency Graph

Create a graph where each ingredient maps to all recipes that depend on it.

For example:

"bread" -> ["sandwich", "burger"]
"meat" -> ["sandwich", "burger"]

This allows us to quickly find which recipes are affected whenever an ingredient becomes available.

We also create an indegree map:

indegree[recipe] = number of ingredients still needed

Initially, this equals the total number of ingredients for each recipe.

Step 2, Initialize the Queue

Insert all initial supplies into a queue.

These are the ingredients already available at the beginning.

We use a queue because this naturally matches breadth first processing of dependencies.

Step 3, Process Available Ingredients

While the queue is not empty:

  1. Remove one available item.
  2. Look up all recipes depending on that item.
  3. Reduce their remaining dependency count.
  4. If a recipe's count becomes zero:
  • Add it to the result list.
  • Push it into the queue because it can now serve as an ingredient for other recipes.

Step 4, Continue Until Exhaustion

Eventually the queue becomes empty.

At this point:

  • Every reachable recipe has been created.
  • Cyclic or impossible recipes remain unresolved because their dependency counts never reach zero.

Why it works

The algorithm maintains the invariant that any item placed into the queue is definitely available.

Initially, this is true for supplies. Later, recipes are only added when every required ingredient has already become available, meaning they are valid to create.

Each dependency is processed exactly once when its ingredient becomes available. Therefore, when a recipe's indegree reaches zero, all its ingredients have been satisfied, guaranteeing correctness.

Cycles naturally fail because none of the involved recipes can reduce their dependency counts to zero unless an external supply breaks the cycle.

Python Solution

from collections import defaultdict, deque
from typing import List

class Solution:
    def findAllRecipes(
        self,
        recipes: List[str],
        ingredients: List[List[str]],
        supplies: List[str]
    ) -> List[str]:

        graph = defaultdict(list)
        indegree = {}

        for recipe, ingredient_list in zip(recipes, ingredients):
            indegree[recipe] = len(ingredient_list)

            for ingredient in ingredient_list:
                graph[ingredient].append(recipe)

        queue = deque(supplies)
        result = []

        while queue:
            current = queue.popleft()

            for recipe in graph[current]:
                indegree[recipe] -= 1

                if indegree[recipe] == 0:
                    result.append(recipe)
                    queue.append(recipe)

        return result

The implementation begins by constructing the dependency graph. Each ingredient stores a list of recipes that require it. This reverse dependency structure is important because when an ingredient becomes available, we immediately know which recipes may now progress toward completion.

The indegree dictionary stores how many ingredients are still required before a recipe can be created. Initially, this equals the total number of ingredients in the recipe.

The queue is initialized with all supplies because these are already available. We then repeatedly process available items.

For every available ingredient or recipe:

  • We examine all recipes depending on it.
  • We decrement their remaining requirement count.
  • If a recipe reaches zero remaining requirements, it becomes creatable.

At that moment, we:

  • Add the recipe to the result.
  • Push it into the queue so it can help create other recipes.

The algorithm naturally handles dependency chains and avoids redundant rescanning.

Go Solution

package main

import "container/list"

func findAllRecipes(recipes []string, ingredients [][]string, supplies []string) []string {
	graph := make(map[string][]string)
	indegree := make(map[string]int)

	for i, recipe := range recipes {
		ingredientList := ingredients[i]
		indegree[recipe] = len(ingredientList)

		for _, ingredient := range ingredientList {
			graph[ingredient] = append(graph[ingredient], recipe)
		}
	}

	queue := list.New()

	for _, supply := range supplies {
		queue.PushBack(supply)
	}

	result := []string{}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		current := front.Value.(string)

		for _, recipe := range graph[current] {
			indegree[recipe]--

			if indegree[recipe] == 0 {
				result = append(result, recipe)
				queue.PushBack(recipe)
			}
		}
	}

	return result
}

The Go implementation follows exactly the same algorithmic structure as the Python version.

A map[string][]string is used for the dependency graph, and map[string]int tracks indegrees.

Go does not provide a built in deque structure equivalent to Python's collections.deque, so container/list is used as a queue.

Slices are dynamically appended when recipes become creatable.

Unlike Python, explicit type assertions are required when retrieving values from the linked list queue.

Worked Examples

Example 1

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

Initial Graph

Ingredient Dependent Recipes
yeast [bread]
flour [bread]

Initial Indegree

Recipe Remaining Ingredients
bread 2

Initial Queue

["yeast", "flour", "corn"]

Processing Steps

Current Item Action Updated Indegree
yeast bread loses one dependency bread = 1
flour bread loses one dependency bread = 0
bread added to result and queue complete
corn no effect unchanged

Final Result

["bread"]

Example 2

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

Initial Indegree

Recipe Remaining Ingredients
bread 2
sandwich 2

Processing

Current Item Effect
yeast bread becomes 1
flour bread becomes 0, enqueue bread
meat sandwich becomes 1
bread sandwich becomes 0, enqueue sandwich

Final Result

["bread", "sandwich"]

Example 3

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

Initial Indegree

Recipe Remaining Ingredients
bread 2
sandwich 2
burger 3

Processing Sequence

Current Item Changes
yeast bread = 1
flour bread = 0
meat sandwich = 1, burger = 2
bread sandwich = 0, burger = 1
sandwich burger = 0
burger complete

Final Result

["bread", "sandwich", "burger"]

Complexity Analysis

Measure Complexity Explanation
Time O(R × I) Each ingredient dependency is processed once
Space O(R × I) Graph and indegree storage

The graph contains one edge for every ingredient dependency. Each edge is visited exactly once during processing.

The queue may contain all supplies and recipes, while the graph stores all dependency relationships. Therefore the total space usage is proportional to the number of dependency edges.

Test Cases

from typing import List

class Solution:
    def findAllRecipes(
        self,
        recipes: List[str],
        ingredients: List[List[str]],
        supplies: List[str]
    ) -> List[str]:

        from collections import defaultdict, deque

        graph = defaultdict(list)
        indegree = {}

        for recipe, ingredient_list in zip(recipes, ingredients):
            indegree[recipe] = len(ingredient_list)

            for ingredient in ingredient_list:
                graph[ingredient].append(recipe)

        queue = deque(supplies)
        result = []

        while queue:
            current = queue.popleft()

            for recipe in graph[current]:
                indegree[recipe] -= 1

                if indegree[recipe] == 0:
                    result.append(recipe)
                    queue.append(recipe)

        return result

solution = Solution()

# Example 1
assert solution.findAllRecipes(
    ["bread"],
    [["yeast", "flour"]],
    ["yeast", "flour", "corn"]
) == ["bread"]

# Example 2
assert solution.findAllRecipes(
    ["bread", "sandwich"],
    [["yeast", "flour"], ["bread", "meat"]],
    ["yeast", "flour", "meat"]
) == ["bread", "sandwich"]

# Example 3
assert solution.findAllRecipes(
    ["bread", "sandwich", "burger"],
    [["yeast", "flour"], ["bread", "meat"], ["sandwich", "meat", "bread"]],
    ["yeast", "flour", "meat"]
) == ["bread", "sandwich", "burger"]

# Impossible recipe due to missing ingredient
assert solution.findAllRecipes(
    ["bread"],
    [["yeast", "flour"]],
    ["yeast"]
) == []

# Cyclic dependency
assert solution.findAllRecipes(
    ["A", "B"],
    [["B"], ["A"]],
    []
) == []

# Recipe chain
assert solution.findAllRecipes(
    ["A", "B", "C"],
    [["x"], ["A"], ["B"]],
    ["x"]
) == ["A", "B", "C"]

# Independent recipes
result = solution.findAllRecipes(
    ["cake", "juice"],
    [["flour"], ["fruit"]],
    ["flour", "fruit"]
)
assert set(result) == {"cake", "juice"}

# Ingredient not in supplies or recipes
assert solution.findAllRecipes(
    ["cake"],
    [["milk", "flour"]],
    ["flour"]
) == []

# Multiple recipes sharing ingredients
result = solution.findAllRecipes(
    ["cake", "bread"],
    [["flour"], ["flour"]],
    ["flour"]
)
assert set(result) == {"cake", "bread"}

# Recipe already effectively available through chain
assert solution.findAllRecipes(
    ["A", "B"],
    [["x"], ["A"]],
    ["x"]
) == ["A", "B"]
Test Why
Single recipe Basic functionality
Chained recipes Verifies recursive creation
Multi level dependencies Tests propagation through graph
Missing ingredient Ensures impossible recipes fail
Cyclic dependency Confirms cycles are not incorrectly resolved
Long dependency chain Verifies repeated queue expansion
Independent recipes Confirms separate components work
Unknown ingredient Ensures unavailable items block creation
Shared ingredients Tests fan out dependency handling
Recipe chain unlocking Verifies recipes become new supplies

Edge Cases

Cyclic Dependencies

A major source of bugs is cyclic recipe dependency.

For example:

A requires B
B requires A

Neither recipe can ever become available unless one is initially provided as a supply.

A naive DFS solution without proper cycle handling may recurse infinitely or incorrectly mark recipes as creatable.

This implementation handles cycles naturally through indegree counting. Since neither recipe's indegree ever reaches zero, neither is added to the queue.

Missing Non Recipe Ingredients

Some ingredients may not exist in either supplies or recipes.

Example:

cake requires milk
milk is nowhere available

A buggy implementation might incorrectly assume every ingredient can eventually be created.

Here, "milk" never enters the queue, so "cake" never reaches indegree zero.

Deep Dependency Chains

Recipes can form long chains:

A -> B -> C -> D

A recursive solution could repeatedly recompute dependencies, leading to inefficiency.

The queue based topological approach processes each dependency exactly once. Once "A" becomes available, it unlocks "B", which unlocks "C", and so on in linear time.