Course Schedule II LeetCode solution in Java

1
class Solution {
2
  public int[] findOrder(int numCourses, int[][] prerequisites) {
3
    Map<Integer, Set<Integer>> graph = new HashMap<>();
4
    int[] inDegree = new int[numCourses];
5
    for (int i = 0; i < numCourses; i++) {
6
      graph.put(i, new HashSet<Integer>());
7
    }
8

9
    for (int[] pair : prerequisites) {
10
      graph.get(pair[1]).add(pair[0]);
11
      inDegree[pair[0]]++;
12
    }
13

14
    // BFS - Kahn's Algorithm - Topological Sort
15
    Queue<Integer> bfsContainer = new LinkedList<>();
16
    for (int i = 0; i < numCourses; i++) {
17
      if (inDegree[i] == 0) {
18
        bfsContainer.add(i);
19
      }
20
    }
21

22
    int count = 0;
23
    int[] ans = new int[numCourses];
24
    while (!bfsContainer.isEmpty()) {
25
      int curr = bfsContainer.poll();
26
      ans[count++] = curr;
27
      for (Integer num : graph.get(curr)) {
28
        inDegree[num]--;
29
        if (inDegree[num] == 0) {
30
          bfsContainer.add(num);
31
        }
32
      }
33
    }
34

35
    if (count < numCourses) {
36
      return new int[] {};
37
    } else {
38
      return ans;
39
    }
40
  }
41
}