LeetCode 210: Course Schedule II

Explanation

To solve this problem, we can use a topological sorting algorithm known as Kahn's algorithm. The algorithm works by finding a valid course ordering by first identifying courses with no prerequisites, updating the prerequisites for other courses accordingly, and repeating the process until all courses are taken.

Here are the steps for the algorithm:

1. Create an adjacency list to represent the graph where each course is a node and each prerequisite is an edge.
2. Initialize an array indegree to store the indegree of each course (number of prerequisites).
3. Initialize a queue queue to store courses with no prerequisites.
4. Add courses with an indegree of 0 to the queue.
5. While the queue is not empty, remove a course from the queue and add it to the result list.
6. For each course removed from the queue, decrease the indegree of its adjacent courses.
7. If any course has an indegree of 0 after decreasing, add it to the queue.
8. Repeat steps 5-7 until the queue is empty.
9. If the result list size is equal to the total number of courses, return the result list. Otherwise, return an empty array.

The time complexity of this algorithm is O(V + E), where V is the number of courses and E is the number of prerequisites. The space complexity is O(V + E) for the adjacency list, indegree array, and queue.

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        int[] indegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for (int[] prerequisite : prerequisites) {
            adjList.get(prerequisite[1]).add(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result.add(course);
            
            for (int nextCourse : adjList.get(course)) {
                indegree[nextCourse]--;
                if (indegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }
        
        if (result.size() == numCourses) {
            return result.stream().mapToInt(Integer::valueOf).toArray();
        } else {
            return new int[0];
        }
    }
}