Course Schedule Iii - Leetcode Solution

Problem Statement:

There are n courses you have to take, labeled from 0 to n-1.

Some of the 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, return the maximum number of courses you can take.

Example 1:

Input: 2, [[1,0]] Output: 2 Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the maximum course you can take is 2.

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: 3 Explanation: There are a total of 4 courses to take. To take course 3 you should have finished courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Therefore the maximum course you can take is 3.

Solution:

The problem can be solved using the concept of Topological Sorting. A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge (u, v) from vertex u to vertex v, u comes before v in the ordering.

Algorithm:

1. Create an adjacency list representation of the given directed graph, where each index i of the list will map to the i-th vertex in the graph and the corresponding list will contain the vertices that the i-th vertex has edges to.

2. Calculate the in-degree of each vertex, which will be the number of edges pointing to the vertex.

3. Create a queue and add all the vertices with an in-degree of 0 to the queue.

4. Initialize a count of the number of visited vertices to 0.

5. While the queue is not empty, remove a vertex from the queue, increment the count of visited vertices, and iterate through all its neighbors.

6. For each neighbor vertex, decrement its in-degree by 1. If the in-degree becomes 0, add it to the queue.

7. Iterate until the queue is empty, and return the count of visited vertices.

Code:

class Solution { public int findOrder(int numCourses, int[][] prerequisites) {

    int[] inDegree = new int[numCourses];
    
    List<List<Integer>> adjList = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        adjList.add(new ArrayList<Integer>());
    }
    
    for (int i = 0; i < prerequisites.length; i++) {
        adjList.get(prerequisites[i][1]).add(prerequisites[i][0]);
        inDegree[prerequisites[i][0]]++;
    }
    
    Queue<Integer> queue = new LinkedList<Integer>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.add(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int curr = queue.poll();
        count++;
        for (int neighbor : adjList.get(curr)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.add(neighbor);
            }
        }
    }
    
    return count == numCourses ? count : 0;
}

}

Time Complexity:

The time complexity of this algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity:

The space complexity of this algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

1