Course Schedule

                                            
// create the adjacency list
const buildAdjacencyList = (totalNodes, graph) =>{
    // makes >>> obj = {key: [], ...}
    const adjacencyList = Array.from({length: totalNodes}, () => []);

    // Loop through the graph grabbing the node in the adjacent node
    for(let [node, adjacentNode] of graph){
        // push the node and it's adjacent node into the adjacency list
        adjacencyList[node].push(adjacentNode);
    };

    // return adjacency list
    return adjacencyList;
};

// check for a cycle
const hasCycle = (node, adjacencyList, visited, departedCount) =>{
    // Mark the nude as visited
    visited[node] = true;

    // loop through the node adjacent nodes
    for(const adjacent of adjacencyList[node]){
        if(!visited[adjacent]){ // if not visited
            visited[adjacent] = true; // mark as visited
            // if has cycle return true
            if(hasCycle(adjacent, adjacencyList, visited, departedCount)) return true;
        }else{
            // Else if departed count equals zero return true
            if(departedCount[adjacent] === 0) return true;
        }
    }

    // if you get here we're departing and we can return false as there is no cycle
    departedCount[node]++;
    return false;
};

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
const canFinish = (numCourses, prerequisites) =>{
    // adjacencyList = {node: [<adjacentNode>, ...], ...}
    const adjacencyList = buildAdjacencyList(numCourses, prerequisites);
    const visited = {};
    // departedCount = {node: 0, ...}
    const departedCount = Array.from({length: numCourses}, () => 0);

    // loop through nodes in adjacency list
    for(let node in adjacencyList){
        if(!visited[node]){ // if not visited and has cycle return false
            if(hasCycle(node, adjacencyList, visited, departedCount)) return false; 
        };     
    }; 

    return true;      
};

To solve this coding challenge, we need to determine whether it is possible to finish all given courses based on the prerequisites. This problem essentially boils down to detecting a cycle in a directed graph. If the graph contains a cycle, you cannot complete all courses, as some courses would be dependent on each other in a circular way.

Step-by-Step Explanation

Create an Adjacency List :

Convert the list of prerequisite pairs into an adjacency list that represents the graph. Each course will point to the courses that depend on it.

Cycle Detection Using DFS :

Utilize Depth-First Search (DFS) to detect cycles in the graph. If a cycle is detected, return

false

, indicating that it's not possible to complete all courses. Use an array or dictionary to keep track of visiting states of the nodes:

Unvisited (0)
Visiting (-1)
Visited (1)

Iterate Through Each Node :

Traverse each course and apply DFS to detect cycles. If no cycles are found in any part of the graph, return

true

Detailed Steps in Pseudocode

Creating the Adjacency List

Initialize : an adjacency list to an empty list for each course.
Populate : the adjacency list with the prerequisites information.

                                            
# Initialize an empty adjacency list 
function createAdjacencyList(totalCourses, prerequisites):
    adjacencyList = list of empty lists of length totalCourses
    
    # Fill adjacency list
    for each (course, prerequisite) in prerequisites:
        append course to the list at index prerequisite in adjacencyList
    
    return adjacencyList

DFS Function for Cycle Detection

Base Case : If a node is being visited (visiting state -1), a cycle is detected.
DFS : Recursively visit all the adjacent nodes.

                                            
# DFS function for detecting cycles
function isCyclic(course, adjacencyList, visitStatus):
    # If the course is in visiting state, cycle detected
    if visitStatus[course] == -1:
        return True
    
    # If the course is already visited once, no need to check again
    if visitStatus[course] == 1:
        return False
    
    # Mark the course as visiting
    visitStatus[course] = -1
    
    # Recursively visit all the adjacent courses
    for adjacentCourse in adjacencyList[course]:
        if isCyclic(adjacentCourse, adjacencyList, visitStatus):
            return True
    
    # Mark the course as visited
    visitStatus[course] = 1
    return False

Main Function

Initialize : List to keep track of visit states.
Iterate : Over all courses and apply the DFS function.

                                            
# Main function that uses DFS to check all nodes
function canFinish(totalCourses, prerequisites):
    # Create the adjacency list for given courses
    adjacencyList = createAdjacencyList(totalCourses, prerequisites)
    
    # Initialize the visit status list
    visitStatus = list of zeros of length totalCourses
    
    # Check for cycles in each course
    for course from 0 to totalCourses - 1:
        if isCyclic(course, adjacencyList, visitStatus):
            return False
    
    return True

Explanation

Adjacency List : This method structures the prerequisites into a more accessible format for graph traversal, where each course is a node, and each prerequisite is a directed edge.
DFS & Cycle Detection : Through Depth-First Search, we can explore each course and its dependencies. By marking nodes with visiting status, we detect cycles if we revisit a course marked as in-progress (-1).
Final Verification : If DFS does not find a cycle for any course, it confirms that all courses can be completed.

This approach ensures that we can efficiently detect if completing all courses is possible based on their prerequisites, leveraging common graph traversal and cycle detection techniques.