Graphs
Course Schedule II
DESCRIPTION (inspired by Leetcode.com)
You have to take a total of numCourses courses, which are labeled from 0 to numCourses - 1. You are given a list of prerequisites pairs, where prerequisites[i] = [a, b] indicates that you must complete course b before course a.
Given the total number of courses and a list of prerequisite pairs, write a function to return the ordering of courses you should take to finish all courses.
If there are multiple valid orderings, return any valid ordering. If it is impossible to finish all courses, return an empty array.
Example 1:
Input:
numCourses = 4 prerequisites = [[1,0], [2,0], [3,1], [3,2]]
Output: [0, 1, 2, 3] or [0, 2, 1, 3]
Explanation: There are a couple of ways to complete all courses, one possible order is [0, 1, 2, 3] and another is [0, 2, 1, 3].
Example 2:
Input:
numCourses = 2 prerequisites = [[1, 0], [0, 1]]
Output: []
Explanation: It is impossible to finish all courses, as you must finish course 0 before course 1 and course 1 before course 0.
public class Solution {
public int[] findOrder(Integer numCourses, int[][] prerequisites) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
We can solve this problem using the same approach as the Course Schedule problem. The only difference is that we need to return the order in which the courses should be taken.
In our solution, we first build a graph representing the prerequisites of each course. We then perform a topological sort on the graph to find the order in which the courses should be taken.
Now, we initialize an empty list called result to store the order of the courses. Each time we dequeue a course from the queue, we add it to the result list to keep track of the ordering of the courses.
Finally, when the queue is empty, we check if the result list has the same length as the number of courses. If it does, we return the result list. Otherwise, we return an empty list, as there is no valid ordering of the courses.
Solution
class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {Map<Integer, List<Integer>> graph = new HashMap<>();int[] inDegree = new int[numCourses];for (int[] prereq : prerequisites) {int dest = prereq[0];int src = prereq[1];graph.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);inDegree[dest]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}List<Integer> order = new ArrayList<>();while (!queue.isEmpty()) {int course = queue.poll();order.add(course);for (int neighbor : graph.getOrDefault(course, new ArrayList<>())) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) {queue.offer(neighbor);}}}return order.size() == numCourses ? order.stream().mapToInt(i -> i).toArray() : new int[0];}}
What is the time complexity of this solution?
O(4ⁿ)
O(V + E)
O(m * n * 4^L)
O(n log n)