Course Schedule Ii

                                            
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> inDegree(numCourses, 0);
        for (auto pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }
        
        queue<int> q;
        vector<int> res;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
                res.push_back(i);
            }
        }
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            for (int next : graph[curr]) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    q.push(next);
                    res.push_back(next);
                }
            }
        }
        
        if (res.size() == numCourses) 
            return res;
        else
            return {};
    }
};

                                            
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        int[] inDegree = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] prerequisite : prerequisites) {
            graph.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);
            }
        }
        
        int index = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            result[index++] = curr;
            for (int next : graph.get(curr)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return index == numCourses ? result : new int[0];
    }
}

                                            
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        from collections import defaultdict, deque
        
        graph = defaultdict(list)
        in_degree = [0] * numCourses
        
        for course, pre in prerequisites:
            graph[pre].append(course)
            in_degree[course] += 1
        
        queue = deque([course for course in range(numCourses) if in_degree[course] == 0])
        result = []
        
        while queue:
            node = queue.popleft()
            result.append(node)
            
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        return result if len(result) == numCourses else []

                                            
public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        List<int>[] graph = new List<int>[numCourses];
        int[] inDegree = new int[numCourses];
        Queue<int> queue = new Queue<int>();
        List<int> result = new List<int>();
        
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var pair in prerequisites) {
            graph[pair[1]].Add(pair[0]);
            inDegree[pair[0]]++;
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            result.Add(course);
            
            foreach (var nextCourse in graph[course]) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    queue.Enqueue(nextCourse);
                }
            }
        }
        
        if (result.Count != numCourses) {
            return new int[0];
        }
        
        return result.ToArray();
    }
}

                                            
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    let adjList = Array.from({ length: numCourses }, () => []);
    let inDegree = Array(numCourses).fill(0);
    
    for (let [course, pre] of prerequisites) {
        adjList[pre].push(course);
        inDegree[course]++;
    }
    
    let queue = [];
    for (let i = 0; i < inDegree.length; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    
    let result = [];
    while (queue.length > 0) {
        let pre = queue.shift();
        numCourses--;
        result.push(pre);
        for (let course of adjList[pre]) {
            inDegree[course]--;
            if (inDegree[course] === 0) queue.push(course);
        }
    }
    
    return numCourses === 0 ? result : [];
};

                                            
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const inDegree: number[] = new Array(numCourses).fill(0);
    const graph: {[key: number]: number[]} = {};
    
    for (let [course, prereq] of prerequisites) {
        inDegree[course]++;
        if (graph[prereq]) {
            graph[prereq].push(course);
        } else {
            graph[prereq] = [course];
        }
    }
    
    const queue: number[] = [];
    for (let i = 0; i < inDegree.length; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    const result: number[] = [];
    while (queue.length > 0) {
        const current = queue.shift();
        result.push(current);
        if (graph[current]) {
            for (let nextCourse of graph[current]) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] === 0) {
                    queue.push(nextCourse);
                }
            }
        }
    }
    
    return result.length === numCourses ? result : [];
};

                                            
class Solution {
    /**
     * @param Integer $numCourses
     * @param Integer[][] $prerequisites
     * @return Integer[]
     */
    function findOrder($numCourses, $prerequisites) {
        $graph = [];
        $indegree = array_fill(0, $numCourses, 0);
        $queue = new SplQueue();
        $result = [];

        foreach ($prerequisites as $pre) {
            $graph[$pre[1]][] = $pre[0];
            $indegree[$pre[0]]++;
        }

        for ($i = 0; $i < $numCourses; $i++) {
            if ($indegree[$i] == 0) {
                $queue->push($i);
                $result[] = $i;
            }
        }

        while (!$queue->isEmpty()) {
            $course = $queue->shift();
            if (isset($graph[$course])) {
                foreach ($graph[$course] as $neighbor) {
                    $indegree[$neighbor]--;
                    if ($indegree[$neighbor] == 0) {
                        $queue->push($neighbor);
                        $result[] = $neighbor;
                    }
                }
            }
        }

        return count($result) == $numCourses ? $result : [];
    }
}

                                            
class Solution {
    func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        var graph: [Int: [Int]] = [:]
        var inDegrees: [Int: Int] = [:]
        var queue: [Int] = []
        var result: [Int] = []

        for i in 0..<numCourses {
            graph[i] = []
            inDegrees[i] = 0
        }

        for edge in prerequisites {
            let course = edge[0]
            let prerequisite = edge[1]
            graph[prerequisite]?.append(course)
            inDegrees[course]? += 1
        }

        for i in 0..<numCourses {
            if inDegrees[i] == 0 {
                queue.append(i)
            }
        }

        while !queue.isEmpty {
            let course = queue.removeFirst()
            result.append(course)

            if let courses = graph[course] {
                for c in courses {
                    inDegrees[c]? -= 1
                    if inDegrees[c] == 0 {
                        queue.append(c)
                    }
                }
            }
        }

        return result.count == numCourses ? result : []
    }
}

                                            
class Solution {
    fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
        val adjList = Array<MutableList<Int>>(numCourses) { mutableListOf() }
        val inDegree = IntArray(numCourses)
        
        for (pre in prerequisites) {
            adjList[pre[1]].add(pre[0])
            inDegree[pre[0]]++
        }
        
        val queue = LinkedList<Int>()
        for (i in 0 until numCourses) {
            if (inDegree[i] == 0) {
                queue.offer(i)
            }
        }
        
        val result = mutableListOf<Int>()
        while (queue.isNotEmpty()) {
            val curr = queue.poll()
            result.add(curr)
            for (next in adjList[curr]) {
                inDegree[next]--
                if (inDegree[next] == 0) {
                    queue.offer(next)
                }
            }
        }
        
        return if (result.size == numCourses) result.toIntArray() else intArrayOf()
    }
}

                                            
import 'dart:collection';

class Solution {
  List<int> findOrder(int numCourses, List<List<int>> prerequisites) {
    List<List<int>> adjacencyList = List.generate(numCourses, (index) => []);
    List<int> inDegree = List.filled(numCourses, 0);
    for (var edge in prerequisites) {
      adjacencyList[edge[1]].add(edge[0]);
      inDegree[edge[0]]++;
    }
    
    List<int> result = [];
    Queue<int> queue = Queue();
    for (var i = 0; i < numCourses; i++) {
      if (inDegree[i] == 0) {
        queue.add(i);
      }
    }
    
    while (queue.isNotEmpty) {
      int current = queue.removeFirst();
      numCourses--;
      result.add(current);
      for (var neighbor in adjacencyList[current]) {
        inDegree[neighbor]--;
        if (inDegree[neighbor] == 0) {
          queue.add(neighbor);
        }
      }
    }
    
    return numCourses == 0 ? result : [];
  }
}

                                            
func findOrder(numCourses int, prerequisites [][]int) []int {
    // Build graph
    graph := make(map[int][]int)
    inDegree := make(map[int]int)
    for _, pre := range prerequisites {
        from, to := pre[1], pre[0]
        graph[from] = append(graph[from], to)
        inDegree[to]++
    }
    
    // Topological sort
    queue := make([]int, 0)
    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
    
    result := make([]int, 0)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    
    if len(result) != numCourses {
        return []int{}
    }
    
    return result
}

                                            
# @param {Integer} num_courses
# @param {Integer[][]} prerequisites
# @return {Integer[]}
def find_order(num_courses, prerequisites)
    indegrees = Array.new(num_courses, 0)
    graph = Array.new(num_courses) { [] }
    result = []
    
    prerequisites.each do |pair|
        course, pre_course = pair
        graph[pre_course].push(course)
        indegrees[course] += 1
    end
    
    queue = []
    indegrees.each_with_index { |degree, i| queue.push(i) if degree == 0 }
    
    while !queue.empty?
        course = queue.shift
        result.push(course)
        graph[course].each do |next_course|
            indegrees[next_course] -= 1
            queue.push(next_course) if indegrees[next_course] == 0
        end
    end
    
    result.size == num_courses ? result : []
end

                                            
object Solution {
    def findOrder(numCourses: Int, prerequisites: Array[Array[Int]]): Array[Int] = {
        val graph = Array.fill(numCourses)(List.empty[Int])
        val inDegree = Array.fill(numCourses)(0)
        val queue = new scala.collection.mutable.Queue[Int]()
        val result = scala.collection.mutable.ListBuffer[Int]()

        prerequisites.foreach(p => {
            graph(p(1)) ::= p(0)
            inDegree(p(0)) += 1
        })

        inDegree.zipWithIndex.foreach {
            case (0, course) => queue.enqueue(course)
            case _ =>
        }

        while (queue.nonEmpty) {
            val course = queue.dequeue()
            result += course

            graph(course).foreach(dependent => {
                inDegree(dependent) -= 1
                if (inDegree(dependent) == 0) {
                    queue.enqueue(dependent)
                }
            })
        }

        if (result.length == numCourses) result.toArray
        else Array.empty[Int]
    }
}

                                            
impl Solution {
    pub fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
        let num_courses = num_courses as usize;
        let mut graph: Vec<Vec<usize>> = vec![vec![]; num_courses];
        let mut indegree: Vec<usize> = vec![0; num_courses];
        let mut queue: Vec<usize> = Vec::new();
        let mut result: Vec<i32> = Vec::new();
        
        for edge in &prerequisites {
            let from = edge[1] as usize;
            let to = edge[0] as usize;
            graph[from].push(to);
            indegree[to] += 1;
        }
        
        for i in 0..num_courses {
            if indegree[i] == 0 {
                queue.push(i);
            }
        }
        
        while let Some(course) = queue.pop() {
            result.push(course as i32);
            for &next in &graph[course] {
                indegree[next] -= 1;
                if indegree[next] == 0 {
                    queue.push(next);
                }
            }
        }
        
        if result.len() == num_courses {
            result
        } else {
            Vec::new()
        }
    }
}

To solve this coding challenge, we need to determine the correct order to take the courses given certain prerequisites. This problem can be effectively approached using Topological Sorting of a Directed Acyclic Graph (DAG). Here are the steps and pseudocode to solve the problem.

Explanation

Graph Representation:

Each course can be represented as a node in a graph. A prerequisite (e.g., to take course 1, you must first complete course 0) can be represented as a directed edge from node 0 to node 1.

In-degree Calculation:

Calculate the in-degree of each node, i.e., the number of edges incoming to a node. This helps us in identifying which nodes (courses) do not have any prerequisites and can be taken first.

Queue Initialization:

Initialize a queue and add all nodes (courses) with in-degree 0. These nodes represent courses that can be taken without completing any other courses.

Topological Sorting using BFS:

Use BFS (Breadth-First Search) to perform the topological sorting. Dequeue a node, add it to the result list, and decrease the in-degree of its neighboring nodes by 1. If in-degree of any neighboring node becomes 0, enqueue that node.

Check for Cycles:

If at the end, the result list contains all courses, then a valid order exists. If not, it means there is a cycle in the graph, making it impossible to complete all courses.

The problem constraints guarantee that the input will not have duplicate prerequisite pairs.

Detailed Steps in Pseudocode

Graph Representation and In-degree Initialization:

Use a dictionary to represent the graph where each key is a course and its value is a list of courses that depend on it.
Initialize an in-degree list where each index represents the in-degree of the corresponding course.

Read Prerequisites:

For each prerequisite pair [ai, bi], add ai to the adjacency list of bi.
Increment the in-degree of ai.

Queue Initialization:

Create a queue and enqueue all courses with in-degree 0.

Topological Sorting:

While the queue is not empty, dequeue a course, add it to the result list.
For each neighboring course, decrease its in-degree by 1.
If the in-degree of any neighboring course becomes 0, enqueue it.

Check Result:

If the length of the result list equals the number of courses, return the result list.
Otherwise, return an empty list indicating it's impossible to complete all courses.

Pseudocode

                                            
# Step 1: Initialize Graph and In-degree list
graph = {}  # Dictionary to store adjacency list
in_degree = []  # List to store in-degree of each course

# Initialize graph and in-degree list to default values
for each course in range(numCourses):
    graph[course] = []  # Each course has an empty list initially
    in_degree[course] = 0  # In-degree is 0 initially

# Step 2: Build Graph & Calculate In-degrees
# Loop through all prerequisites to build graph and in-degree list
for prerequisite in prerequisites:
    course = prerequisite[0]  # Course to be taken 
    prerequisite_course = prerequisite[1]  # Prerequisite course
    graph[prerequisite_course].append(course)  # Append course to adjacency list of prerequisite_course
    in_degree[course] += 1  # Increase in-degree of the course

# Step 3: Initialize queue with nodes of in-degree 0
queue = []  # A queue to help perform BFS
for course in range(numCourses):
    if in_degree[course] == 0:  # If a course has no prerequisites
        queue.append(course)  # Add it to the queue

# Step 4: Execute BFS to get topological order
result = []  # List to store the order of courses
while queue is not empty:
    current_course = queue.pop(0)  # Dequeue the course from the front of the queue
    result.append(current_course)  # Add it to the result list

    # Decrease the in-degree of neighbor nodes (dependent courses)
    for neighbor in graph[current_course]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:  # If in-degree becomes 0, add it to the queue
            queue.append(neighbor)

# Step 5: Check if all courses are taken
if length of result list == numCourses:
    return result  # Return the order of courses
else:
    return []  # Return an empty list indicating it's impvelopment.

By following these detailed steps, we can ensure that all possible prerequisites are met, and we derive a valid order for taking the courses, or determine if it is impossible to complete them all given the constraints and prerequisites.