2115. Find All Possible Recipes from Given Supplies
Approach
Topological sort (Kahn’s) on ingredient dependency graph; collect reachable recipes.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: Topological sort (Kahn’s) on ingredient dependency graph; collect reachable recipes.
// Time: O(V + E) Space: O(V + E)
public class Solution
{
public IList<string> FindAllRecipes(string[] recipes, IList<IList<string>> ingredients, string[] supplies)
{
List<string> ans = new List<string>();
HashSet<string> suppliesSet = new HashSet<string>(supplies);
Dictionary<string, List<string>> graph = new Dictionary<string, List<string>>();
Dictionary<string, int> inDegrees = new Dictionary<string, int>();
// Build the graph.
for (int i = 0; i < recipes.Length; ++i)
{
foreach (var ingredient in ingredients[i])
{
if (!suppliesSet.Contains(ingredient))
{
if (!graph.ContainsKey(ingredient))
graph[ingredient] = new List<string>();
graph[ingredient].Add(recipes[i]);
inDegrees[recipes[i]] = inDegrees.GetValueOrDefault(recipes[i], 0) + 1;
}
}
}
// Perform topological sorting.
Queue<string> q = new Queue<string>(recipes.Where(recipe => inDegrees.GetValueOrDefault(recipe, 0) == 0));
while (q.Count > 0)
{
string u = q.Dequeue();
ans.Add(u);
if (!graph.ContainsKey(u)) continue;
foreach (var v in graph[u])
{
inDegrees[v] = inDegrees.GetValueOrDefault(v, 0) - 1;
if (inDegrees[v] == 0)
q.Enqueue(v);
}
}
return ans;
}
}