Skip to content

2115. Find All Possible Recipes from Given Supplies 👍

  • Time: $O(|V| + |E|)$
  • Space: $O(|V| + |E|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  vector<string> findAllRecipes(vector<string>& recipes,
                                vector<vector<string>>& ingredients,
                                vector<string>& supplies) {
    vector<string> ans;
    unordered_set<string> suppliesSet(supplies.begin(), supplies.end());
    unordered_map<string, vector<string>> graph;
    unordered_map<string, int> inDegree;
    queue<string> q;

    // Build graph.
    for (int i = 0; i < recipes.size(); ++i)
      for (const string& ingredient : ingredients[i])
        if (!suppliesSet.count(ingredient)) {
          graph[ingredient].push_back(recipes[i]);
          ++inDegree[recipes[i]];
        }

    // Topology
    for (const string& recipe : recipes)
      if (!inDegree.count(recipe))
        q.push(recipe);

    while (!q.empty()) {
      const string u = q.front();
      q.pop();
      ans.push_back(u);
      if (!graph.count(u))
        continue;
      for (const string& v : graph[u])
        if (--inDegree[v] == 0)
          q.push(v);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients,
                                     String[] supplies) {
    List<String> ans = new ArrayList<>();
    Set<String> suppliesSet = new HashSet<>();
    for (final String supply : supplies)
      suppliesSet.add(supply);
    Map<String, List<String>> graph = new HashMap<>();
    Map<String, Integer> inDegree = new HashMap<>();

    // Build graph.
    for (int i = 0; i < recipes.length; ++i)
      for (final String ingredient : ingredients.get(i))
        if (!suppliesSet.contains(ingredient)) {
          graph.putIfAbsent(ingredient, new ArrayList<>());
          graph.get(ingredient).add(recipes[i]);
          inDegree.merge(recipes[i], 1, Integer::sum);
        }

    // Topology
    Queue<String> q = Arrays.stream(recipes)
                          .filter(recipe -> inDegree.getOrDefault(recipe, 0) == 0)
                          .collect(Collectors.toCollection(ArrayDeque::new));

    while (!q.isEmpty()) {
      final String u = q.poll();
      ans.add(u);
      if (!graph.containsKey(u))
        continue;
      for (final String v : graph.get(u)) {
        inDegree.merge(v, -1, Integer::sum);
        if (inDegree.get(v) == 0)
          q.offer(v);
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
    ans = []
    supplies = set(supplies)
    graph = collections.defaultdict(list)
    inDegree = collections.Counter()
    q = collections.deque()

    # Build graph.
    for i, recipe in enumerate(recipes):
      for ingredient in ingredients[i]:
        if ingredient not in supplies:
          graph[ingredient].append(recipe)
          inDegree[recipe] += 1

    # Topology
    for recipe in recipes:
      if inDegree[recipe] == 0:
        q.append(recipe)

    while q:
      u = q.popleft()
      ans.append(u)
      for v in graph[u]:
        inDegree[v] -= 1
        if inDegree[v] == 0:
          q.append(v)

    return ans