Find All Possible Recipes from Given Supplies LeetCode solution in Java

1
class Solution {
2
  public List<String> findAllRecipes(
3
      String[] recipes, List<List<String>> ingredients, String[] supplies) {
4
    HashSet<String> sup = new HashSet<>();
5
    HashMap<String, Integer> index = new HashMap<>();
6
    HashMap<String, List<String>> map = new HashMap<>();
7

8
    // create hashset of supplies
9
    for (String s : supplies) {
10
      sup.add(s);
11
    }
12

13
    // store index of all recipes
14
    for (int i = 0; i < recipes.length; i++) {
15
      index.put(recipes[i], i);
16
    }
17

18
    int[] indegree = new int[recipes.length];
19
    // create a mapping of all the recipes that are Ingredients as well
20
    // to the recipes they are ingredients for
21
    for (int i = 0; i < recipes.length; i++) {
22
      for (String need : ingredients.get(i)) {
23
        if (sup.contains(need)) continue;
24

25
        map.putIfAbsent(need, new ArrayList<String>());
26
        map.get(need).add(recipes[i]);
27
        indegree[i]++;
28
      }
29
    }
30

31
    LinkedList<Integer> q = new LinkedList<>();
32
    // add all the recipes with indegree 0 to the queue
33
    for (int i = 0; i < recipes.length; i++) {
34
      if (indegree[i] == 0) {
35
        q.add(i);
36
      }
37
    }
38

39
    List<String> cooked = new ArrayList<>();
40
    while (!q.isEmpty()) {
41
      int i = q.poll();
42
      cooked.add(recipes[i]);
43

44
      if (!map.containsKey(recipes[i])) {
45
        // if the map does not contain this recipe, this means
46
        // this recipe is not an ingredient for any other recipe
47
        // and no further processing is required
48
        continue;
49
      }
50

51
      for (String recipe : map.get(recipes[i])) {
52
        if (--indegree[index.get(recipe)] == 0) {
53
          q.add(index.get(recipe));
54
        }
55
      }
56
    }
57

58
    return cooked;
59
  }
60
}