Description
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 course0you have to first take course1.
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:
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,2,1,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 is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]Solution in Python
Python
from collections import deque, defaultdict
from typing import List
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# Step 1: Create an adjacency list to represent the graph
graph = defaultdict(list)
# Step 2: Create an array to count the in-degrees of each node
in_degree = [0] * numCourses
# Step 3: Populate the graph and in-degree array
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# Step 4: Initialize the queue with courses that have no prerequisites (in-degree 0)
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
# Step 5: Initialize the list to store the course order
order = []
# Step 6: Process the queue
while queue:
# Take the course with no prerequisites
current_course = queue.popleft()
order.append(current_course)
# Decrease the in-degree of neighboring courses
for neighbor in graph[current_course]:
in_degree[neighbor] -= 1
# If a neighboring course now has no prerequisites, add it to the queue
if in_degree[neighbor] == 0:
queue.append(neighbor)
# Step 7: Check if the topological sort includes all courses
if len(order) == numCourses:
return order
else:
# If not all courses are included, return an empty list (indicating a cycle or other issue)
return []Detailed Explanation:
- Graph Representation:
graph: This adjacency list represents the course prerequisites wheregraph[bi]contains all courses that depend on coursebibeing completed first.in_degree: This array tracks the number of prerequisites (in-degree) each course has.
- Populating the Graph and In-Degree Array:
- For each pair in
prerequisites, add the course to the adjacency list for the prerequisite and increment thein_degreeof the course.
- For each pair in
- Initializing the Queue:
- Any course with an in-degree of
0(i.e., no prerequisites) can be taken immediately. These courses are added to the queue to start the process.
- Any course with an in-degree of
- Processing the Queue:
- Courses are processed one by one from the queue:
- The current course is added to the
orderlist. - For each course dependent on the current course (
neighbor), decrease its in-degree. - If a neighbor’s in-degree reaches
0, it means all of its prerequisites are met, so it’s added to the queue.
- The current course is added to the
- Courses are processed one by one from the queue:
- Final Check:
- If the length of
ordermatchesnumCourses, all courses were successfully sorted and the order is returned. - If not, a cycle or other issue prevented some courses from being taken, so an empty list is returned.
- If the length of
This solution runs efficiently with a time complexity of O(V + E), where V is the number of courses and E is the number of prerequisites. It ensures that all courses are taken in an order that respects their prerequisites, and it can detect if it’s impossible to complete all courses (i.e., in the presence of a cycle).
Solution in Javascript
JavaScript
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
var findOrder = function(numCourses, prerequisites) {
// Step 1: Create an adjacency list to represent the graph
const graph = new Map();
// Step 2: Create an array to count the in-degrees of each course
const inDegree = new Array(numCourses).fill(0);
// Step 3: Populate the graph and in-degree array
for (let [course, prereq] of prerequisites) {
// If the graph doesn't have the prerequisite course as a key, add it with an empty array
if (!graph.has(prereq)) {
graph.set(prereq, []);
}
// Add the course to the adjacency list of the prerequisite
graph.get(prereq).push(course);
// Increase the in-degree of the course
inDegree[course]++;
}
// Step 4: Initialize the queue with courses that have no prerequisites (in-degree 0)
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
// Step 5: Initialize the array to store the course order
const order = [];
// Step 6: Process the queue
while (queue.length > 0) {
// Take the course with no prerequisites
const currentCourse = queue.shift();
order.push(currentCourse);
// Decrease the in-degree of neighboring courses
if (graph.has(currentCourse)) {
for (let neighbor of graph.get(currentCourse)) {
inDegree[neighbor]--;
// If a neighboring course now has no prerequisites, add it to the queue
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
}
// Step 7: Check if the topological sort includes all courses
if (order.length === numCourses) {
return order;
} else {
// If not all courses are included, return an empty array (indicating a cycle or other issue)
return [];
}
};Solution in Java
Java
import java.util.*;
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// Step 1: Create an adjacency list to represent the graph
List<List<Integer>> graph = new ArrayList<>();
// Step 2: Create an array to count the in-degrees of each course
int[] inDegree = new int[numCourses];
// Step 3: Initialize the graph with empty lists for each course
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// Step 4: Populate the graph and in-degree array
for (int[] prerequisite : prerequisites) {
int course = prerequisite[0];
int prereq = prerequisite[1];
graph.get(prereq).add(course);
inDegree[course]++;
}
// Step 5: Initialize the queue with courses that have no prerequisites (in-degree 0)
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
// Step 6: Initialize the array to store the course order
int[] order = new int[numCourses];
int index = 0;
// Step 7: Process the queue
while (!queue.isEmpty()) {
// Take the course with no prerequisites
int currentCourse = queue.poll();
order[index++] = currentCourse;
// Decrease the in-degree of neighboring courses
for (int neighbor : graph.get(currentCourse)) {
inDegree[neighbor]--;
// If a neighboring course now has no prerequisites, add it to the queue
if (inDegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
// Step 8: Check if the topological sort includes all courses
if (index == numCourses) {
return order;
} else {
// If not all courses are included, return an empty array (indicating a cycle or other issue)
return new int[0];
}
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
public class Solution {
public int[] FindOrder(int numCourses, int[][] prerequisites) {
// Step 1: Create an adjacency list to represent the graph
List<List<int>> graph = new List<List<int>>();
// Step 2: Create an array to count the in-degrees of each course
int[] inDegree = new int[numCourses];
// Step 3: Initialize the graph with empty lists for each course
for (int i = 0; i < numCourses; i++) {
graph.Add(new List<int>());
}
// Step 4: Populate the graph and in-degree array
foreach (var prerequisite in prerequisites) {
int course = prerequisite[0];
int prereq = prerequisite[1];
graph[prereq].Add(course);
inDegree[course]++;
}
// Step 5: Initialize the queue with courses that have no prerequisites (in-degree 0)
Queue<int> queue = new Queue<int>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.Enqueue(i);
}
}
// Step 6: Initialize the array to store the course order
int[] order = new int[numCourses];
int index = 0;
// Step 7: Process the queue
while (queue.Count > 0) {
// Take the course with no prerequisites
int currentCourse = queue.Dequeue();
order[index++] = currentCourse;
// Decrease the in-degree of neighboring courses
foreach (int neighbor in graph[currentCourse]) {
inDegree[neighbor]--;
// If a neighboring course now has no prerequisites, add it to the queue
if (inDegree[neighbor] == 0) {
queue.Enqueue(neighbor);
}
}
}
// Step 8: Check if the topological sort includes all courses
if (index == numCourses) {
return order;
} else {
// If not all courses are included, return an empty array (indicating a cycle or other issue)
return new int[0];
}
}
}