Problem of The Day: Find All Possible Recipes from Given Supplies
Problem Statement
Intuition
The problem requires determining which recipes can be made given a list of available supplies and dependencies between ingredients and recipes. The natural way to approach this is by treating it as a directed graph problem where recipes depend on ingredients. Recipes can be prepared if all their required ingredients are available in the initial supplies or can be derived from other recipes.
Approach
The approach is based on topological sorting (Kahn’s Algorithm):
- Graph Construction: Construct a directed graph where each ingredient points to the recipes that depend on it. Also, maintain an in-degree dictionary to track dependencies for each recipe.
- Queue Initialization: Start with all the supplies (since they require no dependencies) and add them to a queue.
- Processing Recipes: Perform a BFS-like process where we check recipes whose dependencies are met. If an ingredient is available, reduce the in-degree of dependent recipes. When a recipe’s in-degree becomes zero, it means all required ingredients are available, so we can add it to the queue and eventually to the result.
Complexity
- Time Complexity: \(O(N + M)\) where:
- \(N\) is the number of recipes and ingredients combined (nodes in the graph).
- \(M\) is the number of dependencies (edges in the graph).
- Space Complexity: \(O(N + M)\) for storing the graph and in-degree dictionary.
Code
from collections import deque
from typing import List
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
graph = {}
res = []
queue = deque()
indegree = {}
# Step 1: Build the graph and in-degree dictionary
for i, recipe in enumerate(recipes):
graph[recipe] = graph.get(recipe, [])
for x in ingredients[i]:
graph[x] = graph.get(x, [])
if recipe not in graph[x]:
graph[x].append(recipe)
indegree[recipe] = indegree.get(recipe, 0) + 1
indegree[x] = indegree.get(x, 0)
# Step 2: Initialize the queue with supplies
for node, degree in indegree.items():
if degree == 0 and node in supplies:
queue.append(node)
# Step 3: Process the queue using BFS
while queue:
node = queue.popleft()
if node in recipes:
res.append(node)
for nei in graph[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
return res
Editorial
Approach 1: Breadth-First Search (BFS)
class Solution:
def findAllRecipes(
self,
recipes: list[str],
ingredients: list[list[str]],
supplies: list[str],
) -> list[str]:
# Track available ingredients and recipes
available = set(supplies)
# Queue to process recipe indices
recipe_queue = deque(range(len(recipes)))
created_recipes = []
last_size = -1 # Tracks last known available count
# Continue while we keep finding new recipes
while len(available) > last_size:
last_size = len(available)
queue_size = len(recipe_queue)
# Process all recipes in current queue
while queue_size > 0:
queue_size -= 1
recipe_idx = recipe_queue.popleft()
if all(
ingredient in available
for ingredient in ingredients[recipe_idx]
):
# Recipe can be created - add to available items
available.add(recipes[recipe_idx])
created_recipes.append(recipes[recipe_idx])
else:
recipe_queue.append(recipe_idx)
return created_recipes
Approach 2: Depth-First Search (DFS)
class Solution:
def findAllRecipes(
self,
recipes: list[str],
ingredients: list[list[str]],
supplies: list[str],
) -> list[str]:
# Initialize tracking dictionaries using comprehensions
can_make = dict.fromkeys(supplies, True)
recipe_to_idx = {recipe: idx for idx, recipe in enumerate(recipes)}
def _check_recipe(recipe: str, visited: set) -> bool:
# Already processed and can be made
if can_make.get(recipe, False):
return True
# Not a valid recipe or cycle detected
if recipe not in recipe_to_idx or recipe in visited:
return False
visited.add(recipe)
# Check if all ingredients can be made
can_make[recipe] = all(
_check_recipe(ingredient, visited)
for ingredient in ingredients[recipe_to_idx[recipe]]
)
return can_make[recipe]
# Process each recipe and collect those that can be made
return [recipe for recipe in recipes if _check_recipe(recipe, set())]
Approach 3: Topological Sort (Kahn’s Algorithm)
class Solution:
def findAllRecipes(
self,
recipes: list[str],
ingredients: list[list[str]],
supplies: list[str],
) -> list[str]:
# Store available supplies
available_supplies = set(supplies)
# Map recipe to its index
recipe_to_index = {recipe: idx for idx, recipe in enumerate(recipes)}
# Map ingredient to recipes that need it
dependency_graph = defaultdict(list)
# Count of non-supply ingredients needed for each recipe
in_degree = [0] * len(recipes)
# Build dependency graph
for recipe_idx, ingredient_list in enumerate(ingredients):
for ingredient in ingredient_list:
if ingredient not in available_supplies:
dependency_graph[ingredient].append(recipes[recipe_idx])
in_degree[recipe_idx] += 1
# Start with recipes that only need supplies
queue = deque(idx for idx, count in enumerate(in_degree) if count == 0)
created_recipes = []
# Process recipes in topological order
while queue:
recipe_idx = queue.popleft()
recipe = recipes[recipe_idx]
created_recipes.append(recipe)
# Skip if no recipes depend on this one
for dependent_recipe in dependency_graph[recipe]:
in_degree[recipe_to_index[dependent_recipe]] -= 1
if in_degree[recipe_to_index[dependent_recipe]] == 0:
queue.append(recipe_to_index[dependent_recipe])
return created_recipes
