Skip to content
AI360Xpert
Back to Graphs
Medium

Course Schedule II

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`. 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.

Examples

Input:numCourses = 2, prerequisites = [[1,0]]
Output:[0,1]
To take course 1 you should have finished course 0. So the correct course order is [0,1].
Input:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output:[0,2,1,3]
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 is [0,2,1,3].
Input:numCourses = 1, prerequisites = []
Output:[0]
There are no prerequisites, so taking course 0 is the only valid answer.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Topological Sort (DFS)

Approach

This is an extension of Course Schedule I. Instead of just returning a boolean, we need to return the topological sort of the graph. We use DFS to detect cycles (if a cycle exists, return an empty array) and to build the topological sort. We maintain two sets: `visited` (nodes fully processed and added to the output) and `cycle` (nodes currently in the DFS path). Once all prerequisites of a course are processed (DFS completes for that node), we append the course to our output array.

Complexity Analysis

Time Complexity
O(V + E)
Space Complexity
O(V + E)

Time complexity is O(V + E) as each course and prerequisite is processed once. Space complexity is O(V + E) for the adjacency list and recursion state arrays.

Solution.java
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<>());        }        for (int[] pre : prerequisites) {            adj.get(pre[0]).add(pre[1]);        }                List<Integer> order = new ArrayList<>();        // 0 = unvisited, 1 = visiting (in current path), 2 = visited        int[] state = new int[numCourses];                for (int i = 0; i < numCourses; i++) {            if (!dfs(i, adj, state, order)) {                return new int[0];            }        }                int[] result = new int[numCourses];        for (int i = 0; i < numCourses; i++) {            result[i] = order.get(i);        }        return result;    }        private boolean dfs(int course, List<List<Integer>> adj, int[] state, List<Integer> order) {        if (state[course] == 1) return false; // Cycle detected        if (state[course] == 2) return true;  // Already visited and added                state[course] = 1; // Mark as visiting                for (int pre : adj.get(course)) {            if (!dfs(pre, adj, state, order)) {                return false;            }        }                state[course] = 2; // Mark as visited        order.add(course); // Add to the order        return true;    }}