Similar Problems
Similar Problems not available
Course Schedule Iii  Leetcode Solution
Companies:
LeetCode: Course Schedule Iii Leetcode Solution
Difficulty: Hard
Topics: greedy sorting heappriorityqueue array
Problem Statement:
There are n courses you have to take, labeled from 0 to n1.
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:

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

Calculate the indegree of each vertex, which will be the number of edges pointing to the vertex.

Create a queue and add all the vertices with an indegree of 0 to the queue.

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

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

For each neighbor vertex, decrement its indegree by 1. If the indegree becomes 0, add it to the queue.

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.
Course Schedule Iii Solution Code
1