Course Schedule II medium

Problem Statement

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

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

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

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

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both 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]. Another correct ordering could be [0,2,1,3].

Steps and Explanation

This problem can be solved using Topological Sort. Topological sort is an algorithm for ordering the nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, node A appears before node B in the ordering.

1. Build the Graph: Create an adjacency list to represent the course dependencies. The adjacency list will map each course to a list of its prerequisites.

2. Calculate In-degrees: For each course, calculate its in-degree (the number of courses that have it as a prerequisite).

3. Initialize Queue: Add all courses with an in-degree of 0 to a queue. These are the courses with no prerequisites.

4. Topological Sort:

   • While the queue is not empty:
     • Dequeue a course.
     • Add the course to the result list.
     • For each neighbor (course that depends on the current course):
       • Decrement its in-degree.
       • If its in-degree becomes 0, add it to the queue.

5. Cycle Detection: If the result list's size is less than numCourses, there's a cycle in the graph, meaning it's impossible to finish all courses. Return an empty array in this case.

Code

import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses];

        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[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 neighbor : adj.get(course)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        if (result.size() != numCourses) {
            return new int[0]; // Cycle detected
        }

        int[] resultArray = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;
    }
}

Complexity

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is because we visit each vertex and edge once.

• Space Complexity: O(V + E) to store the adjacency list and in-degree array. The queue and result list also use space proportional to V in the worst case.