Course Schedule

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

• Time: O(N) Space: O(1)

public boolean canFinish(int numCourses, int[][] prerequisites) {
    Queue<Integer> queue = new LinkedList<>();
    int[] indegree = new int[numCourses];
    int counter = 0;
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int[] num : prerequisites) {
        List list = map.containsKey(prerequisite[1]) ? map.get(num[1]) : new ArrayList<>();
        list.add(num[0]);
        map.put(num[1], list);
        indegree[num[0]]++;
    }
    for (int i = 0; i < numCourses; i++)
        if (indegree[i] == 0) queue.offer(i);
    while (!queue.isEmpty()) {
        Integer course = queue.poll();
        counter++;
        if (map.get(course) != null) {
            for (Integer adjacent : map.get(course))
                if (--indegree[adjacent] == 0)
                    queue.offer(adjacent);
        }
    }
    return counter == numCourses;
}