Course Schedule 1

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false. (link)

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= a<sub>i</sub>, b<sub>i</sub> < numCourses

• All the pairs prerequisites[i] are unique.

Solution

This is an application of a topological sort problem.

BFS

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = createAdjList(numCourses, prerequisites);
        int[] indegrees = createIndegrees(numCourses, prerequisites);
        Queue<Integer> queue = createQueue(indegrees);
        List<Integer> order = new ArrayList<>();

        while(!queue.isEmpty()){
            int vertex = queue.poll();
            order.add(vertex);
            for(int edgeVertex : adjList.get(vertex)){
                indegrees[edgeVertex] -= 1;
                if(indegrees[edgeVertex]==0){
                    queue.add(edgeVertex);
                }
            }
        }

        return order.size() == numCourses;
    }

    private Queue<Integer> createQueue(int[] indegrees){
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i=0; i<indegrees.length; i++){
            if(indegrees[i]==0){
                queue.add(i);
            }
        }
        return queue;
    }


    private int[] createIndegrees(int numCourses, int[][] prerequisites){
        int[] indegrees = new int[numCourses];

        for(int[] edge : prerequisites){
            indegrees[edge[0]]+=1;
        }
        return indegrees;
    }

    private List<List<Integer>> createAdjList(int numCourses, int[][] prerequisites){
        List<List<Integer>> adjList = new ArrayList<>();
        for(int i = 0; i<numCourses; i++){
            adjList.add(new ArrayList<>());
        }
        for(int[] edge : prerequisites){
            adjList.get(edge[1]).add(edge[0]);
        }
        return adjList;
    }

}